[ DP ] 비트마스크 (BitMask), BitDp

BitMasking

 

수학에서의 집합은 원소들의 포함 여부를 가진다. 이를 프로그래밍을 통해 표현하기 위해서는 Array 등의 메모리 공간을 이용해서 표현할 수 있다. 이 때, 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법이나, 원소들을 일일이 Array, Vector에 저장하는 방법으로 집합을 포현할 수 있다. 하지만 Array, Vector 등의 여러 원소를 포함하는 Container 뿐만 아니라 다른 방법으로도 집합을 표현할 수 있는데, BitMasking이 그 방법이다.

BitMasking은 정수의 이진수 표현을 이용하여 집합을 나타내는 방법으로, 위에서 설명한 Array로 집합을 표현하는 방식에서 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법을 채택한다. 4 Byte의 Integer를 구성하는 Bit가 0 혹은 1을 가질 수 있기 때문에 각각의 비트의 켜짐 여부(0 or 1)에 따라 집합에 원소가 포함되어 있는지를 체크한다. 당연하게도, 중복되는 원소에 대해서는 그 개수를 표현할 수 없다는 특징이 있기에 Search에서의 방문 여부(비선형 탐색 공간에서의 탐색)를 확인할 때 사용한다.

 

 

---

 

 

 

직접 십진수의 bit를 확인해보며 방식을 이해해보자. 십진수 12를 이진수로 나타내보면 다음과 같다.

 

 

 

 

12 = $2^{3}$ + $2^{2}$ 로 표현되기 때문에 1100으로 나타내어 진다. 이 때 각 비트가 가지는 상태를 통해 집합으로 이용할 수 있다. 비트는 1(True)와 0(False)만을 나타내기 때문에 구성 요소의 존재 여부를 나타낼 수 있는 것이다.

 

 

{0, 1, 2, 3, 4, 5} => 111111 = 63
{0, 1, 3}            => 001011 = 11 
{2, 4, 5}            => 110100 = 52

 

 

위 예시는 보면 집합을 Integer 변수 하나(이진수로 표현됨)로 나타낸 것이다. 값 $i$가 집합에 포함되어 있으면 $i$번 Bit가 1이고, 없으면 0인 것이다.

 

 

이제 집합을 표현하는 방법에 대해 이해했으므로, 합집합, 교집합, 차집합 등의 수학 연산을 구현하는 방법에 대해 익힐 것이다. 이는 비트 연산을 통해 $O(1)$로 구현 가능하며, 이를 Array로 구현했을 때 $O(N)$의 시간복잡도가 나타남을 생각하면 매우 효율적이고 간단한 구현임을 확인할 수 있다.

집합 연산을 구현하기 이전에, 이를 위해 필요한 기본적인 Bit 연산에 대해 살펴보자.

 

 

---

 

Bit Operation

 

 

 

AND Operation

 

AND(&) 연산은 같은 위치의 비트가 둘 다 1이면 1, 하나라도 0이면 0으로 하여 반환하는 연산이다.

 

1100 & 1010 = 1000

 

OR Operation

 

OR(|) 연산은 같은 위치의 비트가 하나라도 1이면 1, 그렇지 않으면 0으로 하여 반환하는 연산이다.

 

1100 | 1010 = 1110

 

XOR Operation

 

XOR 연산(^)은 같은 위치의 비트가 서로 다르다면 1, 아니면 0으로 하여 반환하는 연산이다.

 

1100 ^ 1010 = 0110

 

 

Bit Shift Operation

 

Bit Shift(<<, >>) 연산은 주어진 비트를 오른쪽 또는 왼쪽으로 $i$칸만큼 이동시켜 반환하는 연산으로, <<와 >>에 따라 방향이 결정된다.

 

1010 << 1 = 10100
1100 >> 1 = 0110
1010 >> 2 = 0010
1100 >> 2 = 0011

 

 

NOT Operation

 

Not 연산(~)은 주어진 모든 비트를 0이면 1로, 1이면 0으로 반전시켜 반환한다.

 

~1010 = 0101

 

 

 

 

 

---

 

 

Bit Operation을 이용한 집합 연산의 구현

 

 

원소의 추가 / 삭제

 

Inserting / Removing Element는 집합에서 가장 기본적인 연산이다.

만약 1000(2)에서 1번째 Bit(0번째 비트부터 시작)를 켜고 싶다면, 즉 원소 1을 집합에 추가하고 싶다면, 1000(2)을 0010(1<<1)과 OR 연산을 한 결과를 취하면 된다.

또한 1010(2)에서 1번째 비트를 끄고 싶다면, 즉 원소 1을 집합에서 삭제하고 싶다면, 1010(2)과 1101(~(1<<1))을 AND 연산한 결과를 취하면 된다.

 

bit |= (1<<idx) // Inserting i (i번째 비트 켜기)
bit &= ~(1<<idx) // Removing i (i번째 비트 끄기)

 

 

원소 i의 존재 여부 확인

 

원소 i가 존재하는지 여부( i번째 Bit가 켜졌는지 여부 )를 확인하는 방법은 원소를 추가, 삭제하는 것보다 더욱 간단하다. i번째 비트만 1인 Integer과 AND 연산한 결과가 0인지 아닌지에 따라서 결정된다.

 

 

if( bit & (1<<idx) ){
    cout << idx << "번 비트가 켜져있습니다.\n";
}
if( !(bit & (1<<idx)) ){
     cout << idx << "번 비트가 꺼져있습니다.\n";
}

 

 

 

Other Operation

 

합집합, 교집합, 차집합을 구하는 방법 또한 위에서 원소를 추가/삭제했던 것처럼 하면 된다. 합집합은 OR 연산을 통해 간단하게 구현할 수 있고, 교집합은 AND 연산을 이용한다. 차집합은 원소를 삭제했던 방법과 같이, 두 집합 A, B(A, B는 Integer)에 대해 A와 ~B를 AND 연산하면, A에서 켜진 비트 중, B에도 존재하는 비트는 모두 꺼지게 된다.

 

 

 

그 외에도 C/C++의 내장 함수가 존재하여 다양한 비트에 관한 함수를 지원한다.

 

__builtin_clz(x): 왼쪽에 연속해서 있는 비트 0의 개수 반환

__builtin_ctz(x): 오른쪽에 연속해서 있는 비트 0의 개수 반환

__builtin_popcount(x): 비트 1의 개수 반환

 

 

 

 

---

 

Bit DP & Problems

 

 

Bitmasking을 이용하면 집합을 표현할 수 있기 때문에 DFS에서 사용되는 visited Array (방문 여부 표시 배열)을 Integer 변수 1개만으로 표현할 수 있다. 다만 Integer 변수로 표현할 수 있는 비트의 개수는 32개 뿐이므로 방문 여부를 표현 가능한 원소의 개수가 제한적이라는 단점이 있다. 그럼에도 불구하고, Array로만 표현 가능했던 집합을 정수형 변수 1개로만 표현할 수 있으므로 N의 범위가 작은 Bruteforce 문제에서 사용할 수 있다. 특히, 집합(방문 여부)를 표현하는 변수를 memoization의 인자로 사용하면 DP를 통해 Bruteforce 문제를 더욱 효율적으로 해결할 수 있게 된다. 만약 방문 여부를 Array로 표현하면 memoization의 인자로 사용하기 어렵다는 한계를 극복하는 것이다. 이렇듯, 탐색 과정에서 집합의 갱신이 존재할 때, 그 상태를 DP의 인자로 저장하기 위해 BitMasking을 사용하는 기법을 BitMasking DP / Bit DP라고 한다.

 

 

 

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

 

이 문제가 Bit DP의 가장 대표적인 문제로, N개의 도시와 방문 비용을 알고 있을 때 최소 비용으로 모든 도시를 순회해서 다시 1번 도시로 돌아오기 위한 최소 비용을 구하는 문제이다.

 

 

Bruteforce 기법이나 DFS 등을 통해 탐색을 한다면 Array를 사용하던, BitMasking을 사용하던, 방문 여부를 표시하는 전형적인 탐색 방법을 통해 문제를 해결할 수 있지만 시간복잡도가 $O(N!)$로 매우 느리다. 모든 도시를 방문하는 것이므로, 1부터 N까지의 수를 이용해 순열을 만드는 경우의 수와 같은 시간복잡도를 가지기 때문이다. 하지만 이러한 시간복잡도로는 위 문제를 해결할 수 없다.

 

일단 Bruteforce 기법으로 재귀 함수를 구성한다면 함수의 인자를 x(현재 방문한 도시), bit(도시 방문 여부를 나타내는 집합)로 표현할 수 있다. 이제 여기에 DP를 적용하여 memoization array를 정의하면

 

memo[x][bit] : 현재 방문한 도시가 x이고 도시 방문 여부의 정수가 bit일 때, 순회 후 1로 돌아가 얻을 수 있는 최소 비용

 

으로 정의할 수 있고, 아래와 같이 구현할 수 있게 된다.

 

 

 

#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
 
int N;
int W[16][16];
int memo[16][1<<16];
 
int dp(int x, int bit)
{
    if(bit==(1<<N)-1){
        return W[x][0]!=0 ? W[x][0] : INF;
    }
    if(memo[x][bit]!=-1) return memo[x][bit];
    memo[x][bit]=INF;
    for(int i=0; i<N; i++){
        if(W[x][i]!=0 && !(bit&(1<<i))){
            memo[x][bit]=min(memo[x][bit], dp(i, bit|(1<<i))+W[x][i]);
        }
    }
    return memo[x][bit];
}
 
int main()
{
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            scanf("%d", &W[i][j]);
        }
    }
    memset(memo, -1, sizeof(memo));
    printf("%d\n", dp(0, 1));
    return 0;
}

 

 

코드에서 dp 함수의 종료 조건을 보면

 

 

if(bit==(1<<N)-1){
    return W[x][0]!=0 ? W[x][0] : INF;
}

 

 

bit와 (1<<N)-1을 비교하는 조건문이 있는데, 만약 N=3일 때라고 가정해보면, (1<<N)은 1000(2)이므로 (1<<N)-1은 0111(2)이다. 이는 3개의 비트가 1로 되어있는, 즉 3개의 모든 도시를 방문한 상태를 나타낸다.

 

 

따라서 현재 모든 도시를 방문했는지 확인 하는 조건문을 통과하면, 현재 도시에서 1번 도시(편의상 코드에선 0번부터 시작한다)로 가는 비용을 반환한다.

 

 

 

연산 부분을 보면

 

 

for(int i=0; i<N; i++){
    if(W[x][i]!=0 && !(bit&(1<<i))){
        memo[x][bit]=min(memo[x][bit], dp(i, bit|(1<<i))+W[x][i]);
    }
}

 

 

만약 갈 수 있는 도시이고(W 값이 0이 아니면), 아직 방문하지 않은 도시라면(bit에 $i$가 속해있지 않다면) 방문해준다.

 

bit&(1<<i)는 i번째 비트가 켜져있는지 확인하는 연산으로 앞에 !를 붙여주어서 비트가 꺼져있는지를 확인한다.

 

dp(i, bit|(1<<i))+W[x][i] 는 bit의 $i$번째 비트를 1로 바꾸어 주고 재귀 호출을 진행한다.

 

 

 

 

아래는 Bit DP에 대한 문제들로, 핵심적인 문제의 요구 사항은 N개의 원소를 탐색하여 최댓값 / 최솟값을 구하는 것으로, 위에서 보았던 외판원 순회와 형태가 거의 비슷하다.

 

 

BOJ 1086 박성원: 비트 마스킹의 대표적인 문제 (풀이)

BOJ 9305 Yahtzee: 비트 마스킹을 이용한 dp 문제로, 탐색 방법은 이전 문제들과 거의 비슷하지만 재귀 호출을 위한 여러 조건을 고려해야하는 구현이 까다로운 문제 (풀이)