비트마스킹 - 비트 연산을 활용한 집합 표현 - soo:bak

작성일 :

비트마스킹이란?

{A, B, C, D} 4개 원소 중 일부를 선택하는 상황을 생각해보겠습니다. 선택 가능한 조합은 {}, {A}, {B}, {A,B}, … , {A,B,C,D} 까지 총 16가지(2⁴)입니다.


이 16가지 조합을 배열이나 집합 자료구조로 표현할 수도 있지만, 정수 하나로 표현하는 방법이 있습니다. 각 원소의 선택 여부를 0과 1로 나타내면, 4비트 이진수로 모든 조합을 표현할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11

원소:     D  C  B  A
비트:     3  2  1  0

0000 (0)  → { }
0001 (1)  → {A}
0010 (2)  → {B}
0011 (3)  → {A, B}
0100 (4)  → {C}
...
1101 (13) → {A, C, D}
1111 (15) → {A, B, C, D}


비트마스킹(Bitmask)은 이처럼 정수의 이진수 표현을 이용하여 집합을 표현하는 기법입니다. 집합의 각 원소를 비트 하나에 대응시켜, 원소의 포함 여부를 0과 1로 나타냅니다.


왜 비트마스킹을 사용하는가?

1. 메모리 효율성

20개 원소의 부분집합을 표현한다고 가정해보겠습니다.

  • 배열 사용: 각 부분집합마다 최대 20개 원소를 저장해야 함
  • 비트마스크 사용: 정수 하나(20비트)로 표현 가능


2. 연산 속도

집합 연산(합집합, 교집합, 차집합 등)을 비트 연산 한 번으로 처리할 수 있습니다.

1
2
3

// 배열로 합집합: O(n)
// 비트마스크로 합집합: O(1)
int unionSet = A | B;


3. DP 상태 표현

“어떤 원소들을 선택했는가”를 DP의 상태로 사용할 때, 정수 하나로 깔끔하게 표현할 수 있습니다.

예를 들어, 외판원 문제(TSP)에서 dp[방문한_도시_집합][현재_도시]를 사용합니다.


비트 연산자

비트마스킹을 사용하려면 비트 연산자를 이해해야 합니다.


AND (&)

두 비트가 모두 1일 때만 1을 반환합니다.

1
2
3
4

  1101 (13)
& 1010 (10)
--------
  1000 (8)

활용: 특정 비트가 켜져있는지 확인, 교집합


OR (|)

두 비트 중 하나라도 1이면 1을 반환합니다.

1
2
3
4

  1101 (13)
| 1010 (10)
--------
  1111 (15)

활용: 특정 비트 켜기 (원소 추가), 합집합


XOR (^)

두 비트가 다르면 1을 반환합니다.

1
2
3
4

  1101 (13)
^ 1010 (10)
--------
  0111 (7)

활용: 특정 비트 토글 (있으면 제거, 없으면 추가), 대칭 차집합


NOT (~)

모든 비트를 반전합니다.

1

~0000 1101 = 1111 0010 (2의 보수 표현)

주의: 결과는 음수가 됩니다. 특정 범위에서만 사용할 때는 AND와 함께 사용합니다.


왼쪽 시프트 («)

비트를 왼쪽으로 이동합니다. 오른쪽은 0으로 채워집니다.

1
2

1 << 3 = 0001 → 1000 (8)
5 << 2 = 0101 → 10100 (20)

활용: 2의 거듭제곱 계산(1 << n = 2ⁿ), 특정 위치 비트 생성


오른쪽 시프트 (»)

비트를 오른쪽으로 이동합니다.

1
2

1101 >> 2 = 0011 (3)
20 >> 1 = 10 (10)

활용: 2로 나누기, 특정 비트 위치 확인


비트마스크 기본 연산

집합을 비트마스크로 표현할 때 자주 사용하는 연산들입니다.


1. 원소 추가 (i번째 비트 켜기)

1

mask |= (1 << i);

예: mask = 1001에서 1번 비트 추가 → mask = 1011


2. 원소 제거 (i번째 비트 끄기)

1

mask &= ~(1 << i);

예: mask = 1011에서 1번 비트 제거 → mask = 1001


3. 원소 확인 (i번째 비트가 켜져있는지)

1
2
3

if (mask & (1 << i)) {
  // i번 원소가 포함됨
}


4. 원소 토글 (있으면 제거, 없으면 추가)

1

mask ^= (1 << i);


5. 최하위 켜진 비트 구하기

1

int lowest = mask & (-mask);

예: mask = 1100이면 lowest = 0100 (4)


6. 최하위 켜진 비트 끄기

1

mask &= (mask - 1);

예: mask = 1100이면 mask = 1000

이 연산은 켜진 비트의 개수를 세거나, 켜진 비트를 하나씩 순회할 때 유용합니다.


7. 켜진 비트 개수 세기

1
2

int count = __builtin_popcount(mask);    // int용
int count = __builtin_popcountll(mask);  // long long용


비트마스크 활용 예시

1. 부분집합 순회

n개 원소의 모든 부분집합(2ⁿ개)을 순회합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 4;
  
  // 0부터 2^n - 1까지가 모든 부분집합
  for (int mask = 0; mask < (1 << n); mask++) {
    cout << "mask=" << mask << ": { ";
    for (int i = 0; i < n; i++) {
      if (mask & (1 << i))
        cout << i << " ";
    }
    cout << "}\n";
  }
  
  return 0;
}

출력:

1
2
3
4
5
6
7

mask=0: { }
mask=1: { 0 }
mask=2: { 1 }
mask=3: { 0 1 }
mask=4: { 2 }
...
mask=15: { 0 1 2 3 }


2. 특정 집합의 부분집합만 순회

집합 mask의 모든 부분집합을 순회합니다. 이 기법은 집합 DP에서 자주 사용됩니다.

1
2
3
4
5
6
7
8

int mask = 13; // 1101 = {0, 2, 3}

// mask의 부분집합만 순회 (빈 집합 제외)
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
  cout << sub << ": ";
  // sub를 출력하는 코드
}
// 출력: 13, 12, 9, 8, 5, 4, 1

빈 집합(0)도 포함하려면 별도로 처리합니다.


3. 부분집합의 합 문제

n개의 정수 중 일부를 선택하여 합이 target이 되는 경우의 수를 구합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> arr = {1, 2, 3, 4, 5};
  int n = arr.size();
  int target = 7;
  int count = 0;
  
  for (int mask = 0; mask < (1 << n); mask++) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
      if (mask & (1 << i))
        sum += arr[i];
    }
    if (sum == target)
      count++;
  }
  
  cout << count << "\n";  // 3 ({2,5}, {3,4}, {1,2,4})
  
  return 0;
}


비트마스크 DP

비트마스크는 DP에서 방문한 상태나 선택한 원소를 표현할 때 특히 유용합니다.


외판원 문제 (TSP)

n개의 도시가 있고, 각 도시 간 이동 비용이 주어집니다. 모든 도시를 정확히 한 번씩 방문하고 출발점으로 돌아오는 최소 비용을 구합니다.


상태 정의

dp[mask][i] = 방문한 도시 집합이 mask이고, 현재 도시가 i일 때의 최소 비용


점화식

다음 도시 j로 이동하는 경우:

1

dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])


구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int n;
int dist[20][20];
int dp[1 << 20][20];

int tsp(int mask, int cur) {
  // 모든 도시 방문 완료
  if (mask == (1 << n) - 1)
    return dist[cur][0];  // 출발점으로 돌아가는 비용
  
  // 이미 계산한 상태
  if (dp[mask][cur] != -1)
    return dp[mask][cur];
  
  int result = INF;
  for (int next = 0; next < n; next++) {
    // 이미 방문한 도시는 건너뜀
    if (mask & (1 << next))
      continue;
    
    // next 도시 방문
    int newMask = mask | (1 << next);
    result = min(result, dist[cur][next] + tsp(newMask, next));
  }
  
  return dp[mask][cur] = result;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> dist[i][j];
    }
  }
  
  memset(dp, -1, sizeof(dp));
  
  // 0번 도시에서 출발
  cout << tsp(1, 0) << "\n";
  
  return 0;
}


시간 복잡도: O(2ⁿ × n²)

  • 상태의 수: 2ⁿ × n
  • 각 상태에서 다음 도시 선택: O(n)

공간 복잡도: O(2ⁿ × n)


n이 20이면 2²⁰ × 20 × 20 ≈ 4억이므로, n ≤ 20 정도까지 해결 가능합니다.


비트마스킹의 장점

장점 설명
공간 효율성 집합을 정수 하나로 표현
연산 속도 비트 연산은 CPU에서 매우 빠름
간결한 코드 집합 연산을 한 줄로 표현 가능
DP 상태 표현 선택/방문 상태를 깔끔하게 표현


주의사항

1. 원소 개수 제한

  • int: 32비트이므로 최대 32개 원소
  • long long: 64비트이므로 최대 64개 원소

원소가 더 많으면 bitset을 사용하거나 다른 방법을 고려해야 합니다.


2. 시프트 연산 시 타입 주의

1
2
3
4
5

// ❌ 잘못된 예: 1은 int이므로 32비트 범위를 넘으면 오버플로우
int mask = 1 << 35;

// ✅ 올바른 예: 1LL은 long long
long long mask = 1LL << 35;


3. 음수 주의

NOT 연산(~)의 결과는 음수가 됩니다. 특정 비트만 반전하려면:

1
2

// n비트 범위 내에서만 반전
int inverted = mask ^ ((1 << n) - 1);


마무리

비트마스킹은 집합을 정수로 표현하여 효율적인 연산을 가능하게 합니다.


연산 비트마스크 표현
원소 추가 mask \|= (1 << i)
원소 제거 mask &= ~(1 << i)
원소 확인 mask & (1 << i)
합집합 A \| B
교집합 A & B
차집합 A & ~B


특히 n이 20 이하인 집합 관련 DP 문제에서 비트마스킹은 매우 유용합니다.


관련 문제

이 블로그의 다른 글