[알고리즘] 비트마스킹 C++

내가 보려고 정리함...

1. 집합 표현하기

집합 표현하기는 비트를 이용한 아주 간단한 아이디어다.

{1,2,5}이라는 집합이 있을 때
우리는 1,2,5 번째에 해당하는 비트를 1로 두고 나머지를 0으로 둬서 집합을 표현할 수 있다.
따라서 00.. 10011로 표현될 것이다.

그럼 정수 범위가 0 ≤ Ai < 2^25 = 33554432 인 집합이 주어질 때 집합을 비트로 표현해 보자.

우선 최대 범위인 33554431이라는 원소가 주어진다면 이 위치에 비트를 1로 설정해야 하기 때문에 33554431 개의 비트가 필요하다.

C++에는 이렇게 많은 비트를 쉽게 나타낼 수 있는 비트 셋이라는 것이 존재한다.

또한 비트 셋은 여러 가지 유용한 메서드와 연산자를 제공한다.
간단하게 [idx] 연산자는 idx 자릿수에 해당하는 비트에 접근할 수 있고
set(idx) 메서드는 idx 자릿수에 해당하는 비트를 1로 만들 수 있다.

#include <bitset>

bitset<(1 << 25)> set;

(1 << 25)는 2^25를 나타내고 이것을 비트 셋의 인자로 전달하면 비트 셋을 33554432개의 비트를 가진 비트 셋을 생성한다.

그럼 이제 우리에게 {1,3,3,200000}라는 집합이 주어졌고 중복을 제거하라는 조건이 주어졌다고 치자.

간단하게 우리는 1부터 200000 원소까지 하나씩 입력받으면서 중복은 입력받지 않으면 된다.

#include <iostream>
#include <bitset>

int main() {
  bitset<(1 << 25)> set;

  int input;
  while(scanf("%d", &input) != EOF) {
      if(!set[input]) {
          set[input] = 1; // 또는 set.set(input);
          printf("%d ", input);
      }
  }
}

이렇게 하면 중복을 제거하면서 쉽게 집합을 나타낼 수 있다.

예시로 든 문제는 백준에 골드 3 13701번 중복 제거 문제이다.

2. 모든 부분집합 구하기

백준 문제를 풀다 보면 부분집합을 구할 일이 자주 있다.

우선 코드부터 보자.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> arr = {1,2,3,4} // 주어진 집합
	int size = arr.size();
    
    for(int i = 0; i < (1 << size); i++) {
    	for(int j = 0; j < size; j++) {
        	if(i & (1 << j)) {
            	cout << arr[j] << " ";
            }
            cout << endl;
        }
    }
}

간단하게 설명하면 i를 2진수로 표현했을 때 (1 << j)와 AND 연산을 해서 1이 나오면 arr[j]에 해당하는 원소를 출력하는 방법이다.

자세한 설명이 궁금하다면 https://royhelen.tistory.com/29 이 블로그를 참고하는 게 좋을 것 같다.