5-11. DP: State Compression (비트마스크)

1. 상태 압축 (State Compression)의 이해

동적 프로그래밍(DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 부분 문제의 해를 저장(메모이제이션)하여 중복 계산을 피하는 강력한 알고리즘 기법입니다. DP를 적용할 때, 중요한 것 중 하나는 문제의 "상태(State)"를 어떻게 정의하고 표현할 것인가입니다. 상태는 부분 문제의 해를 결정하는 데 필요한 정보를 담고 있으며, 상태를 효율적으로 표현하는 것은 DP 알고리즘의 성능에 큰 영향을 미칩니다.

상태 압축(State Compression)은 DP에서 상태의 수가 너무 많아 메모리나 계산 시간 측면에서 비효율적인 경우, 상태를 압축하여 표현하는 기법입니다. 특히, 상태를 표현하는 데 필요한 정보가 boolean 타입의 값들로 구성되어 있을 때, 즉, 어떤 요소가 "있다/없다" 와 같이 두 가지 상태만을 가질 때, 비트마스크(Bitmask)를 사용하여 상태를 효과적으로 압축할 수 있습니다.

비트마스크는 정수를 사용하여 각 비트(bit)를 특정 상태를 나타내는 데 사용합니다. 예를 들어, 8개의 요소를 가진 집합의 부분 집합을 표현한다고 가정해 봅시다. 각 요소의 존재 여부를 1 또는 0으로 나타내면, 8개의 비트를 사용하여 총 256가지(2⁸)의 부분 집합을 표현할 수 있습니다. 이러한 방식으로, 여러 개의 boolean 값을 하나의 정수로 압축하여 메모리 사용량을 줄이고, 비트 연산을 통해 상태를 효율적으로 조작할 수 있습니다.

2. 비트마스크 (Bitmask)의 기본 원리

비트마스크는 각 비트가 특정 정보를 나타내는 정수입니다. 비트마스크를 이해하기 위해서는 다음의 기본적인 비트 연산자들을 알아야 합니다.

• & (AND): 두 비트가 모두 1일 때만 1을 반환합니다.
• | (OR): 두 비트 중 하나라도 1이면 1을 반환합니다.
• ^ (XOR): 두 비트가 다를 때 1을 반환합니다.
• ~ (NOT): 비트를 반전시킵니다 (0 -> 1, 1 -> 0).
• << (Left Shift): 비트를 왼쪽으로 이동시킵니다. x << y는 x를 왼쪽으로 y비트 이동시키는 것을 의미합니다.
• >> (Right Shift): 비트를 오른쪽으로 이동시킵니다. x >> y는 x를 오른쪽으로 y비트 이동시키는 것을 의미합니다.

1) 비트 설정 (Setting a bit)

특정 비트를 1로 설정하는 방법은 OR 연산자를 사용합니다.

number |= (1 << bit_position);

예를 들어, number의 3번째 비트를 1로 설정하려면 다음과 같이 합니다. (bit_position은 0부터 시작)

int number = 0; // 00000000
int bit_position = 3;
number |= (1 << bit_position); // number = 00001000 (8)

2) 비트 해제 (Clearing a bit)

특정 비트를 0으로 설정하는 방법은 AND 연산자와 NOT 연산자를 사용합니다.

number &= ~(1 << bit_position);

예를 들어, number의 3번째 비트를 0으로 설정하려면 다음과 같이 합니다.

int number = 8; // 00001000
int bit_position = 3;
number &= ~(1 << bit_position); // number = 00000000 (0)

3) 비트 확인 (Checking a bit)

특정 비트가 1인지 0인지 확인하는 방법은 AND 연산자를 사용합니다.

if (number & (1 << bit_position)) {
    // bit_position 번째 비트가 1일 때 실행
}

예를 들어, number의 3번째 비트가 1인지 확인하려면 다음과 같이 합니다.

int number = 8; // 00001000
int bit_position = 3;
if (number & (1 << bit_position)) { // 00001000 & 00001000 == 00001000 (true)
    // 3번째 비트가 1일 때 실행
}

4) 비트 토글 (Toggling a bit)

특정 비트의 값을 반전시키는 방법은 XOR 연산자를 사용합니다 (0 -> 1, 1 -> 0).

number ^= (1 << bit_position);

3. DP와 비트마스크의 결합: 예시 문제

비트마스크를 활용하는 DP 문제는 다양한 형태로 나타날 수 있습니다. 대표적인 예시 문제를 통해 비트마스크를 어떻게 DP에 적용하는지 살펴보겠습니다.

1) 외판원 순회 문제 (Traveling Salesperson Problem, TSP) - 간략화된 버전

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

상태 정의:

• dp[mask][city]는 mask에 해당하는 도시들을 방문했고, 마지막으로 방문한 도시가 city일 때, 출발 도시로 돌아오는 데 필요한 최소 비용을 나타냅니다.
• mask는 비트마스크로, 각 비트가 해당 도시의 방문 여부를 나타냅니다. 예를 들어, mask의 i번째 비트가 1이면 도시 i를 방문했음을 의미합니다.

점화식:

dp[mask][city] = min(dp[mask ^ (1 << city)][prev_city] + cost[prev_city][city])

• mask ^ (1 << city): 현재 mask에서 city를 방문하지 않은 상태로 만듭니다.
• cost[prev_city][city]: prev_city에서 city로 이동하는 비용.

초기 조건:

• dp[(1 << start_city)][start_city] = 0 (출발 도시에서 출발)
  • start_city는 출발 도시를 의미

코드 (C++):

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<vector<int>> cost(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> cost[i][j];
        }
    }

    int start_city = 0; // 출발 도시
    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9)); // 1e9는 무한대를 나타냄
    dp[1 << start_city][start_city] = 0;

    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int city = 0; city < n; ++city) {
            if (mask & (1 << city)) { // city를 방문한 경우
                for (int prev_city = 0; prev_city < n; ++prev_city) {
                    if (prev_city != city && (mask & (1 << prev_city))) { // 이전 도시와 현재 도시가 다르고, 이전 도시를 방문한 경우
                        dp[mask][city] = min(dp[mask][city], dp[mask ^ (1 << city)][prev_city] + cost[prev_city][city]);
                    }
                }
            }
        }
    }

    // 모든 도시를 방문하고 출발 도시로 돌아오는 최소 비용 계산
    int final_mask = (1 << n) - 1; // 모든 도시를 방문한 상태
    int min_cost = 1e9;
    for (int city = 0; city < n; ++city) {
        min_cost = min(min_cost, dp[final_mask][city] + cost[city][start_city]);
    }

    cout << min_cost << endl;

    return 0;
}

위 코드는 TSP 문제를 비트마스크 DP로 해결하는 기본적인 예시입니다. dp[mask][city]를 이해하는 것이 핵심입니다. mask는 현재까지 방문한 도시들의 집합을 비트마스크로 표현하고, city는 마지막으로 방문한 도시를 나타냅니다. 점화식을 통해 이전 상태에서 현재 상태로의 최소 비용을 계산하고, 최종적으로 모든 도시를 방문하고 출발 도시로 돌아오는 최소 비용을 찾습니다.

2) 비트마스크를 이용한 Submask Iteration

비트마스크를 사용하는 또 다른 중요한 기술은 Submask Iteration입니다. 특정 마스크의 모든 부분집합(submask)을 효율적으로 순회하는 방법입니다. 예를 들어, 마스크가 10110인 경우, 00000, 00010, 00100, 00110, 10000, 10010, 10100, 10110 과 같은 모든 부분집합을 순회하는 것입니다. 이를 통해, 어떤 집합의 부분 집합에 대한 정보를 빠르게 확인할 수 있습니다.

for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
    // submask를 사용하여 작업 수행
}
// submask가 0인 경우도 처리

Submask Iteration을 사용하면 TSP와 같은 문제에서 다양한 부분 문제에 대한 정보를 빠르게 계산하고, 최적해를 찾는 데 도움을 줍니다. 이 기법은 상태 압축을 사용하는 DP 문제의 성능을 크게 향상시킬 수 있습니다.

4. 비트마스크 DP 문제 해결 전략

비트마스크를 활용한 DP 문제를 효과적으로 해결하기 위한 몇 가지 전략을 제시합니다.

1) 상태 정의

• 문제를 분석하여 각 상태를 정의합니다.
• 상태를 구성하는 요소가 boolean 값으로 표현될 수 있는지 확인합니다.
• 비트마스크를 사용하여 각 상태를 압축할 수 있는지 확인합니다.

2) 점화식 설계

• 문제의 특성을 파악하여 현재 상태를 이전 상태로부터 어떻게 계산할 수 있는지 정의합니다.
• 비트 연산을 활용하여 상태 간의 관계를 표현합니다.
• 초기 조건을 설정합니다.

3) 구현

• 비트 연산을 사용하여 상태를 조작합니다 (설정, 해제, 확인 등).
• Submask Iteration과 같은 기술을 활용하여 부분 문제를 효율적으로 처리합니다.
• 메모이제이션 또는 탭ulated 방식을 사용하여 DP를 구현합니다.

4) 최적화

• 필요에 따라 메모리 사용량을 최적화합니다.
• 비트 연산의 효율성을 고려하여 코드를 작성합니다.

5. 주의사항 및 트러블슈팅

1) 정수 오버플로우

비트마스크는 정수를 사용하므로, 비트마스크의 크기가 커지면 정수 오버플로우가 발생할 수 있습니다. 예를 들어, 32비트 정수형을 사용하는 경우, 32개 이상의 요소를 표현하는 비트마스크를 사용할 수 없습니다. 이 경우, long long과 같은 더 큰 정수형을 사용해야 합니다.

2) 비트 연산의 우선순위

비트 연산의 우선순위는 다른 연산자에 비해 낮을 수 있습니다. 따라서, 비트 연산을 수행할 때 괄호를 사용하여 명시적으로 우선순위를 지정하는 것이 좋습니다. 예를 들어, x & 1 << i와 같은 표현은 x & (1 << i)로 변경하는 것이 안전합니다.

3) 메모리 사용량

비트마스크를 사용하는 DP는 상태 공간이 커질 수 있습니다. 특히, dp[mask][...]와 같은 형태의 DP 배열을 사용하는 경우, mask의 크기가 커지면 메모리 사용량이 급증할 수 있습니다. 메모리 제한에 유의하여, 불필요한 메모리 사용을 줄이는 방안을 고려해야 합니다.

4) 디버깅

비트마스크를 사용하는 DP는 디버깅이 어려울 수 있습니다. 각 비트의 의미를 정확하게 파악하고, 비트 연산의 결과를 예상하는 것이 중요합니다. 디버깅을 위해 비트마스크의 값을 출력하거나, 각 비트의 의미를 주석으로 명시하는 것이 도움이 될 수 있습니다.

6. 결론

비트마스크를 활용한 상태 압축은 DP 문제를 해결하는 데 있어서 강력한 도구입니다. 상태 공간을 효율적으로 표현하고, 비트 연산을 통해 상태를 조작함으로써, 다양한 문제를 효과적으로 해결할 수 있습니다. 하지만, 정수 오버플로우, 메모리 사용량, 디버깅 등의 주의사항을 염두에 두고 문제 해결 전략을 세워야 합니다. 비트마스크 DP는 알고리즘 문제를 해결하는 데 있어 숙련도를 높이는 데 기여할 것이며, 다양한 실전 문제에서 그 진가를 발휘할 것입니다.