동적 계획법 (DP) 과 비트 마스킹 (Bit Masking)

동적 계획법 (DP) 와 비트 마스킹 (Bit Masking)

프로그래밍 문제를 풀기 위해 비트 마스킹을 쓰실때는 비트 마스킹 자체가 일반적으로 지수 형태의 시간 복잡도와 메모리를 잡아먹기 때문에, 적은 제약조건(small constraints) 을 설정하고 쓰시는것이 좋습니다.

첫째로, 비트 마스크(Bitmask) 란 무엇인지 알아보겠습니다. 비트마스크에서 마스크(Mask) 는 뭔가를 숨긴다는 의미입니다. 비트 마스크는 어떤 무엇을 이(2)진수의 형태로 표현한 것입니다. 예를 들어보겠습니다. 어떤 집합 $A$ 는 다음과 같습니다. $A = \{1,2,3,4,5\}$. 우리는 이 집합 $A$ 를 길이가 $5$ 인 비트마스크를 이용해서 나타낼 수 있습니다. 이때 $i$ 번째 $(0\leq i \leq 4)$ 비트(bit) 가 활성화 되었다는 의미는 해당 집합 $A$ 의 부분집합에 $i$ 번째 원소가 들어있다는 의미입니다. 그래서 비트 마스크 $01010$ 은 부분집합 $\{2,4\}$ 를 의미합니다.

비트 마스크는 어떤 집합의 요소들의 구성 여부를 표현하는데 유용합니다. 이제는 이 비트마스크를 활용하여, 비트 마스크의 장점을 살펴보겠습니다. 우리는 $i$ 번째 비트를 활성화 하거나, $i$ 번째 비트를 해제할 수 있습니다. 그리고 $i$ 번째 비트가 활성화 되있는지 안되어 있는지 확인할 수도 있습니다. 비트마스크를 $b = 01010$ 이라고 해보겠습니다.

1. $i$번째 비트 활성화하기 : $b \ |\ (1 \lt\lt i)$
예를 들어, $i = 0 $ 이라고 하겠습니다. 그렇다면 $0$ 번째 비트마스크를 활성화 하는 방법은 다음과 같습니다.

$(1 \lt\lt i) = 00001$

$01010\ | \ 00001 = 01011 $

위의 연산을 통해 이제 비트마스크는 $0$번째 원소를 포함하게 되었습니다. 즉, 부분집합으로 표현하면 $\{1,2,4\}$ 입니다.

2. $i$ 번째 비트 해제하기 : $b \ \& \ !(1 \lt\lt i)$
이제는 $i = 1$ 이라고 가정하겠습니다. $1$ 번째 비트 마스크를 해제하는 방법은 다음과 같습니다.

$(1 \lt\lt i ) = 00010$

$!(1\lt\lt i) = 11101$

$01010 \ \& \ 11101 = 01000 $

이제 비트마스크는 $1$ 번째 원소를 포함하지 않게되었습니다. 즉, 부분집합으로 표현하면 $\{4\}$ 입니다. 잘 생각해보면 비트를 활성화 하기위해 비트연산하는 부분에 부정(not) 을 취하면 비트를 해제하는 연산으로 바뀐다는 것을 확인하실 수 있습니다.

$$!(\ | \ (1\lt\lt i)) = \& \ !(1 \lt\lt i)$$

3. $i$ 번째 비트가 활성화 되어있는지 확인하기 : $b \ \& \ (1 \lt\lt i)$
이 연산을 통해서 $i$ 번째 비트가 활성화 되어있다면, 우리가 $3.$ 의 연산을 통해서 0 이 아닌 정수의 결과값을 얻게 될 것입니다. 만약 활성화 되어있지 않다면, 0 을 얻습니다. $i = 3$ 이라고 가정하겠습니다. $3$ 번째 비트가 활성화 되어있는지 확인해 보는 연산은 다음과 같습니다.

$(1\lt\lt i) = 01000$

$01010 \ \& \ 01000 = 01000$

명확히 $01000$ 은 $0$ 이 아닙니다. 그렇기에 $3$ 번째 원소는 현재 부분집합에 포함되어 있다고 볼 수 있겠네요.

이제 문제를 통해 비트마스크를 활용해 보는 시간을 가져보겠습니다.

집합과 어떤 하나의 값이 주어졌을때, 주어진 집합에서 만들 수 있는 부분집합이 가지고 있는 원소들의 총 합이 주어진 값과 같거나 큰 부분집합의 총 갯수를 세기.

solve(set, set_size, val)
    count = 0		// 최종 출력값
    for x = 0 to power(2, set_size)
        sum = 0     // 부분 집합에 들어있는 원소들의 총 합
        for k = 0 to set_size        
        	// 집합 x 에 있는 k 번째 비트가 활성화 되있다면 (위의 3번)
            if k th bit is set in x		
                sum = sum + set[k]
        if sum >= val		// 주어진 값보다 크면 갯수를 센다.
             count = count + 1
    return count

가장 바깥에 있는 for loop 는 주어진 집합 크기가 $n$ 이라 한다면, $0$ 부터 $2^{n}-1$ 까지의 부분집합의 종류를 모두 확인하는 과정을 거칩니다. (예를 들어, 크기가 2개라면 $00, 01, 10, 11$ 총 $4$개)

비트마스크를 단순히 적용한 위의 솔루션은 $O(2^n * n)$ 의 시간복잡도를 가집니다. 꽤 오래 걸리죠.

이제 이 시간복잡도를 단축하기 위해 동적 계획법과 비트 마스키를 섞어서 다른 문제를 풀어보도록 하겠습니다.

문제

여기 $N$ 명의 사람과 $N$ 개의 작업이 있습니다. 각 작업은 단 한명의 사람에게만 수행될 수 있습니다. 또한 $N \times N$ 크기의 비용이 적힌 2차원 행렬 역시 주어집니다. $cost[i][j]$ 에는 사람 $i$ 가 작업 $j$ 를 맡기위해 얼마나 많은 비용을 주어야 하는지 적혀있습니다. 이제 우리가 할 일은 각 사람들에게 작업을 부여하면서 부담해야하는 비용을 최소화 해야 합니다. 중요한 점은 각 작업은 오직 한명에게만 할당되고, 각 인원은 오직 하나의 작업만을 맡아야 합니다.

이 문제를 풀기위한 가장 단순한 접근법은 모든 할당 방법을 전부 찾아보는것입니다.
알고리즘은 다음과 같습니다.

assign(N,  cost)
    for i = 0 to N
        assignment[i] = i            // 사람 i 에게 i 작업을 할당함.
    res = INFINITY
    for j = 0 to factorial(N)
        total_cost = 0
        for i = 0 to N
            total_cost = total_cost + cost[i][assignment[i]]
        res = min(res, total_cost)
        다음 수열 조합을 생성해 내는 function(assignment) 
    return res

$j$ 번째 사람에게 특정 비용이 드는 $i$ 번째 작업을 맡긴다는것은 단순히 사람들이 순서대로 열거된 배치를 이리저리 바꿔보는것과 같습니다.

예를 들어 총 3명의 사람이 있다고 가정하고 {1,2,3} 으로 집합을 정하겠습니다. 그렇다면, 사람 1은 1번째 작업을 맡게되고 사람2는 2번째, 사람 3은 3번째 작업을 맡게되는 것입니다. {3, 2, 1} 이라 한다면 3번째 사람은 1번째 작업을 맡게되겠네요.

이렇게 작업을 맡기기 위한 주어진 수열의 경우의 수는, 사람과 작업이 $N$ 개 있을때, $N!$ 번의 조합으로 계산할 수 있습니다. 그렇기 때문에 시간복잡도 역시 $O(N!)$ 가 됩니다. 딱 봐도 좋지않아 보입니다.

이 솔루션을 동적 계획법(DP) 를 사용해 향상시켜 보겠습니다. DP 는 이미 계산된 값을 이용해서 새로운 값을 찾아내므로, 이전에 계산된 값을 저장하는 상태 (state) 를 표현하기 위해 $(k,mask)$ 를 사용하겠습니다. $k$ 는 사람을 배열의 index 형식으로 표현했을때, 사람 $0$ 부터 $k-1$ 까지 할당한 총 사람의 '명' 수를 나타냅니다. 그리고 $mask$ 는 $i$ 번째 비트를 통해 $i$ 번째 작업이 할당되었는지 되지 않았는지 알려주는 이진수로 표현됩니다.

예를 들어 $answer(k,mask)$ 까지 답을 알았다고 가정하겠습니다. 이 뜻은, 사람 $0$ 부터 $k-1$ 까지 총 $k$ 명에게 작업에 할당되었을때 필요한 최소의 비용을 구했다고 말할 수 있습니다. 이제, 사람 $k$ 에게 작업을 할당할 차례라고 하겠습니다. 만약, $i$ 번째 작업이 어떤 사람에게도 할당되어지지 않았다면 (즉, $mask \ \& \ (1 << i) = 0$ 이라면), 이 $i$ 번째 작업은 $k$ 번의 사람에게 할당되어야 할것입니다. (모든 $N$ 개의 작업은 모든 $N$ 명의 사람에게 할당되어야 합니다.) 그리고 그 $i$ 번째 작업을 할당할때 $k$ 번째의 사람이 처리하기 위한 최소의 비용을 찾으면 됩니다.

$$answer(k+1, mask|(1 \lt\lt i)) = min(answer(k+1, mask|(1 \lt\lt i)), answer(k,mask)+cost[k][i])$$

아래의 코드를 보면 아시겠지만, 작업을 하는사람은 바깥쪽 for loop 로 고정되지만 작업 자체는 안쪽 for loop 를 통해 $i$ 번째의 작업은 매번 바뀝니다. 그렇기에 $k$ 번째의 사람은 어느 작업을 맡느냐에 따라 처리 비용이 달라지고 그 비용중 최소를 찾으면 되는것이겠죠.

또 한 가지 중요한것은 $k$ 는 언제나 $mask$ 의 총 bit 길이와 같은 값을 가진다는 것입니다. 사람에게 작업을 할당하든 안하든 $mask$ 에는 $0$ 또는 $1$ 의 bit가 붙을것이고 동시에 $k$ 역시 늘어나기 때문이지요. 그래서 우리는 $k$ 를 지울 수 있습니다. 이제 상태를 표현할때 $k$ 없이 $(mask)$ 만으로 표현할 수 있습니다. 그리고 다시 한번 위의 수식을 써보겠습니다. $answer(mask)$ 는,

$$answer(mask|(1 \lt\lt i)) = min(answer(mask|(1 \lt\lt i)), answer(mask)+cost[x][i])$$

로 표현될 수 있습니다. 여기서 $x$ 는 $mask$ 에 있는 bits 집합의 총 개수 입니다.

이제 완성된 알고리즘을 보겠습니다.

assign(N, cost)
    for i = 0 to power(2,N)
        dp[i] = INFINITY
    dp[0] = 0				// base case : 어떤 사람도 작업을 할당받지 않음.
    for mask = 0 to power(2, N)
        x = count_set_bits(mask)
        for j = 0 to N
            if jth bit is not set in i
                dp[mask|(1<<j)] = min(dp[mask|(1<<j)], dp[mask]+cost[x][j])
    return dp[power(2,N)-1]   

위 알고리즘의 시간복잡도는 $O(2^n n)$ 입니다. 그리고 공간복잡도는 $O(2^n)$ 입니다. 위 문제는 DP 와 비트마스킹을 이용한 하나의 문제에 불과합니다. 이와 같은 종류의 문제는 굉장히 많습니다. 만약 그래프가 주어지고 그 그래프가 해밀턴 경로 (이에 대한 포스팅은 나중에 하도록 하겠습니다.) 를 포함하는지 찾아내는 문제가 주어진다면, 이 역시 DP 와 비트마스킹으로 풀 수 있고, 그 솔루션의 시간복잡도는 $O(2^n n^2)$ 이고 공간복잡도는 $O(2^n n)$ 입니다.

---

비트마스킹을 집어넣었더니 조금 더 어려워 진것 같습니다.
이에 관련된 문제를 포스팅 해보겠습니다. 해밀턴 경로도요..!