[C++로 배우는 알고리즘과 자료구조 심화] Day 19: 스테이트 컴프레션 동적 계획법 (State Compression DP)

스테이트 컴프레션 동적 계획법 (State Compression DP)

스테이트 컴프레션 동적 계획법(State Compression DP)은 상태를 비트마스크로 표현하여 동적 계획법을 적용하는 기법입니다. 이는 주로 부분 집합 문제나 조합 최적화 문제에 사용됩니다. 이 기법은 상태를 효율적으로 관리하고, 메모리 사용량을 줄일 수 있습니다.

문제 예시: 여행 계획

주어진 도시들을 방문하면서 최소 비용으로 여행 계획을 세우는 문제를 해결하기 위해 스테이트 컴프레션 DP를 사용할 수 있습니다. 여기서 dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.

스테이트 컴프레션 DP 구현

다음은 C++로 스테이트 컴프레션 DP를 사용하여 문제를 해결하는 예제입니다.

#include <iostream>
#include <vector>
#include <climits>

// 도시 수 최대값
const int MAX_N = 20;

// 거리 행렬
int dist[MAX_N][MAX_N];

// DP 테이블
int dp[1 << MAX_N][MAX_N];

// 도시 수
int n;

// 스테이트 컴프레션 DP 함수
int travelPlan(int mask, int pos) {
    if (mask == (1 << n) - 1) {
        return dist[pos][0]; // 모든 도시를 방문한 후 시작점으로 돌아감
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int answer = INT_MAX;

    for (int city = 0; city < n; ++city) {
        if ((mask & (1 << city)) == 0) {
            int newAnswer = dist[pos][city] + travelPlan(mask | (1 << city), city);
            answer = std::min(answer, newAnswer);
        }
    }

    return dp[mask][pos] = answer;
}

int main() {
    std::cout << "도시 수를 입력하세요: ";
    std::cin >> n;

    std::cout << "도시 간의 거리를 입력하세요:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> dist[i][j];
        }
    }

    // DP 테이블 초기화
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = -1;
        }
    }

    int result = travelPlan(1, 0); // 시작점은 도시 0
    std::cout << "최소 여행 비용: " << result << std::endl;

    return 0;
}

 

설명

1. 입력:
   • n: 도시 수
   • dist: 도시 간의 거리 행렬
2. 비트마스크 DP 테이블:
   • dp[mask][i]는 방문한 도시 집합이 mask이고 현재 i 도시에 위치한 경우의 최소 비용을 의미합니다.
   • 초기값으로 -1을 설정하여 아직 계산되지 않은 상태를 표시합니다.
3. 비트마스크와 재귀 함수:
   • mask는 현재 방문한 도시들을 이진수로 나타낸 것입니다. 예를 들어, mask = 5 (0101)은 도시 0과 2를 방문했음을 나타냅니다.
   • pos는 현재 위치한 도시입니다.
   • 모든 도시를 방문한 상태 (mask == (1 << n) - 1)에서 시작 도시로 돌아가는 비용을 반환합니다.
   • 이미 계산된 상태는 DP 테이블을 참조하여 반환합니다.
   • 아직 방문하지 않은 도시를 방문하여 최소 비용을 계산합니다.

스테이트 컴프레션 동적 계획법의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 20: 배낭 문제 변형(Multiple Knapsack, Unbounded Knapsack)"에 대해 학습하겠습니다.