[백준 14939번 , 1208번] 백준 문제로 배우는 비트 마스킹
비트 마스킹 (bit masking) 이란?
이진수와 관련된 개념이다
이진수 110 은 2^2+2^1 으로 십진수 6을 표현한다.
그리고 이진수는 또다른 원론적인 의미로 해석될 수 있는데 바로 true false다.
즉 110 은 단순 십진수 6 뿐 아니라, 첫째, 둘째 놈은 true, 셋째 놈은 false 로 의미 부여를 하고 갈 수 도 있는것.
이번엔 거꾸로 가보자. 눈앞에 10개 버튼이 있는데, 나는 각버튼을 누를 수 도, 누르지 않을 수도 있다.
내가 버튼을 누를 수 있는 경우의 수는?
간단한 수학이다. 누른다, 안누른다 = 2
2^10= 1024 가지 경우의 수가 나온다.
아래 이진수에 부여한 의미를 생각해보자
0000000000 == 십진수 0 >> 전부 버튼을 누르지 않는다 0000000001 == 십진수 1 >> 마지막 버튼만 누른다
0000000000 == 십진수 0 11111111111 == 십진수 1023
만약 우리가 루프를 통해 0~ 1023 ( 2^10-1 ) 까지 돌 때 해당 십진수를 이진수로 생각하면 어떻게 될까?
모든 가짓수를 구할 수있는 것이다.
여기서 우리가 십진수에 이진수적 개념 ( n째 비트가 0인가 1인가? ) 을 사용했기에, 우리가 n째 비트를 추출하는 것도 가능해야한다. 이때 쓰이는 것이 비트 마스킹이다.
1bit 변수 a,b를 생각해보자.
a & b a,b 가 모두 1이어야 비트 1을 리턴
a|b >> a,b 중 하나만 1이어도 비트 1을 리턴
!a >> 비트를 뒤집는다 ( 0> 1 , 1>0 )
여기까지보면 바로 아하! 할거다. 그냥 우리가 쓰던 && , ||, !를 비트에 씌운거다.
우리가 볼 문제 백준 14939 에선 이중 & 가 쓰인다.
미지의 열자리 이진수 A에 대해
A& 000001111 의미는 하위 4비트 만 그대로 두고 나머진 제거하라는 의미다.
이걸 이용하면 0~ 1023의 십진수에서 우리가 원하는 n쨰 비트의 값만 뽑아낼 수 있다.
ex) A& 0000000001 >> 맨 오른쪽 비트만 추출.
이런식으로 & 는 특정 비트를 추출할 때 쓰인다.
그럼 이제 간단한 예제를 풀어보자.
프로그래머스- 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
numbers 내의 모든 수를 + or - 하는 모든 경우의 수를 비트마스킹으로 고려할 수 있다.
1: +
0: -
예를 들어 '1100' 은 numbers의 0,1 째 수를 + 하고, 2,3 째 수를 - 하는 경우의 수를 나타낸다.
#include <string>
#include <vector>
#include<math.h>
using namespace std;
int solution(vector<int> numbers, int target) {
int answer = 0;
int max_num=pow(2,numbers.size());
for(int i=0;i<max_num;i++){
int sum=0;
for(int k=0;k<numbers.size();k++){
if( (i&(1<<k) )!=0){
sum+=numbers[k];
}else{
sum-=numbers[k];
}
}
if(sum==target)
answer++;
}
주의
if(bit & (1<<i)!=0){ // -> 연산우선순위로 인해 bit & (1<<i) 가 먼저 구해지지 않아서 오답!!
}
if( ( bit & (1<<i) )!=0){ //(bit & (1<<i)) 이런식으로 비트 연산을 묶어줘야한다!!!
}
이번엔 백준 사이트의 14939번 문제를 풀어보자!
https://www.acmicpc.net/problem/14939
14939번: 불 끄기
전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄
www.acmicpc.net
이 문제는 주석을 아주 자세히 적어놨으니 한번 풀어보고 모르겠으면 주석을 참고하자!
main문을 먼저 읽고 그때 그때 나오는 함수를 따라가 주석을 읽으면 이해하기 편하다.
//비트 마스킹
#include<iostream>
using namespace std;
bool arr[100][100];
bool origin[100][100];
char c;
int dx[5] = {0, 0,1,0,-1 };
int dy[5] = {0, 1, 0, -1, 0 };
//각 전구의 스위치는 최대 1번만 눌러야 최소 값 나온다 ( 2번누르면 원래대로 돌아감)
// 따라서 스위치를 누르는 순서는 결과에 영향이 없다!!
void click(int x, int y) {
for (int i = 0; i < 5; i++) {
if (!((0 > x + dx[i]) || (x + dx[i] >= 10) || (0 > y + dy[i]) || (y + dy[i] >= 10))) {//범위 밖으로 나간건 무시.
//arr[x + dx[i]][y + dy[i]] = ( !(arr[x + dx[i]][y + dy[i]]) ); //클릭된곳 전부 뒤집기.(자신,상,하,좌,우)
if (arr[x + dx[i]][y + dy[i]])
arr[x + dx[i]][y + dy[i]] = false;
else
arr[x + dx[i]][y + dy[i]] = true;
}
}
}
int go() {
int cnt = 0;
for (int i = 1; i < 10; i++) {//첫줄은 앞에서 구함.
for (int j = 0; j < 10; j++) {
if (arr[i - 1][j]) { //윗 전구 켜저있으면 무조건 꺼야한다.
click(i, j);
cnt++;
} //만약 윗줄이 꺼져있는데 누른다면, 윗줄을 켜버린다. 따라서 윗줄이 꺼져있으면 클릭하지 않는다.
}
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
if (arr[i][j])return -1;// 하나라도 켜져있으면 전부 끄기 실패!
}
return cnt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ans = 987654321,tmp,cnt2;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cin >> c;
c != '#' ? (arr[i][j] = true) : (arr[i][j] = false);
origin[i][j] = arr[i][j];
}
}
for (int bit = 0; bit < 1024; bit++) { // 2진수 0000000000 ~ 1111111111 ( 각 위치의 전구를 누르거나, 누르지 않거나 따져봄
for (int i = 0; i < 10; i++) { //경우의 수 완료 후 다시 배열 초기화 후 진행.
for (int j = 0; j < 10; j++) {
arr[i][j] = origin[i][j];
}
}
cnt2 = 0;//첫줄에 눌린 스위치 수
//첫째 줄이 확정된 상태라면 ,다음 줄 부터는 윗줄의 전구를 끄는 경우의 수만 적용되야한다!
//('모든 전구를 끌 경우의수' 윗줄을 다 못끈 상태에서 다음줄로 넘어가면 못 끈 윗줄을 끌 수 없게 된다.
for (int i = 0; i < 10; i++) {// 각각 첫째 bit ~ 마지막 bit 만 추출한다.
if (bit & (1 << i)) {//내가 눌리는 경우의수라면
click(0, i);
cnt2++;
}
}
tmp= go();
if (tmp != -1 && ans > (tmp+cnt2)) {
ans = tmp+cnt2;
}
}
if (ans != 987654321)
cout << ans;
else
cout << -1;
}
한 문제를 더 해보자
백준 1208번 문제를 보고오자!
해당 문제는 제약이 없다면 그냥 비트마스킹을 이용한 완전 탐색으로 2^n개의 모든 부분집합의 합을 구한다음
그 값이 s 인걸 찾으면 된다.
하지만 이 문제는 일반적인 방식으로 풀면 시간초과 + 공간 복잡도 초과가 발생한다.
따라서 해당 집합을 2 덩이로 나눈다. 각 집합의 이름을 l(왼쪽 ) r (오른쪽) 으로 칭하겠다.
L과 R의 모든 부분 집합의 합을 구하고 l의 모든 부분집합의 합을 la에 저장 하고 r의 모든 부분 집합의 합을 ra에 저장한다.
la의 i 째 값 la[i] 에 대해서, 해당 값을 통해 S 가 완성 되려면, S-la[i] 의 값을 ra에서 가져와야한다.
따라서 lower_bound와 upper_bound 를 통해 ra안의 S-i 의 개수를 구하면 la와 ra에서 1개씩 뽑아서 S가 나오는 가짓수가 나온다.
+ 만약 l, 혹은 r의 부분집합만으로 S 가나온다면?
우리는 비트마스킹으로 '모든' 부분집합의 합을 구했고, 이는 공집합도 포함한다. 따라서 부분집합의 합이 '0' 인 것도 포함된다. 이 경우에는 la 혹은 ra의 값만으로 S 가 나오는 경우의 수도 포함되기에 상관없다!
아래 코드에 주석을 자세히 달아놓았으니 참고하자!
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
//절반으로 나눠 모든 부분합 구한뒤, 각 그룹별 1개씩 뽑아
//https://blog.naver.com/gmlwo308/222081888774
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, s,tmp;
cin >> n >> s;
int m = n / 2;
vector<int> l, r,la,ra;
for (int i = 0; i < m; i++) {
cin >> tmp;
l.push_back(tmp);
}
for (int i = m ; i < n; i++) {
cin >> tmp;
r.push_back(tmp);
}
for (int i = 0; i < (1 << l.size());i++) { //2^n개 모든 부분집합 찾기 시작
int sum = 0;
for (int j = 0; j < l.size(); j++) {
if ( i & 1<<j ) {//해당 비트가 켜저있으면 0 이 아닌 값이 나온다! ( 1x )
sum += l[j];
}
}
la.push_back(sum);
}
for (int i = 0; i < (1 << r.size()); i++) { //2^n개 모든 부분집합 찾기 시작
int sum = 0;
for (int j = 0; j < r.size(); j++) {
if ((i & 1<<j) ) {
sum += r[j];
}
}
ra.push_back(sum);
}
sort(ra.begin(), ra.end());// 이진 탐색 위해 오른쪽 집합 정렬
long long ans = 0;
for (long long i : la) { // s-i + i ==s s-i는 왼쪽 집합과 더해져 S완성되는 수
auto l = lower_bound(ra.begin(),ra.end(), s - i); //s-i와 같거나 큰 수 가 나오는 첫 위치
auto u = upper_bound(ra.begin(),ra.end(), s - i); //s-i보다 큰 수 가 나오는 첫위치
ans += u - l; //upperbound-lower bound 는 ra에서 값이 s-i인 값의 개수.
}
if (s == 0)
ans -= 1;
cout << ans << endl;
}