[백준 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

프로그래머스

 

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번: 불 끄기

이 문제는 주석을 아주 자세히 적어놨으니  한번 풀어보고 모르겠으면 주석을 참고하자!

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;
	
	
}