핵심 원리
- dp는 sub-problem의 결과를 통해 최적 상위(optimal parent) problem을 해결하는 구조여야 합니다. 즉, 계산의 순서가 보장되어야 한다는 것이에요.
- for loop를 통해 0부터 1<<n 까지 iterating 하면서 각 bitmask에 0~n번째 작업을 추가로 할당하여 sub-problem을 먼저 계산하게 함으로써 위 조건이 만족됩니다. 여기서 submask가 아닌 sub-problem이라고 한 이유는 특정 bitmask에 대한 submask ‘만’ 먼저 계산하는건 아니기 때문이에요.
비트마스크 DP 접근법 설명
상태 표현 (State Representation)
dp[mask]: mask에 표현된 작업들을 할당했을 때의 최소 비용(0 ⇐ mask ⇐ 2^n)- mask의 각 비트는 해당 작업이 할당되었는지(1) 아닌지(0)를 나타냄(1001: 4번째, 1번째 일이 할당됨, 누구한테 할당된 것인지는 모르고 dp state 안에 최소 비용인 채로 녹아있죠)
점화식 (Recurrence Relation)
- 각 상태에서, 현재 할당할 작업자는 mask의 비트 수(popcount)로 결정됨
- 이 작업자에게 할당할 수 있는 모든 미할당 작업을 시도함
구현 구조
cpp
// DP 배열 초기화 (최대값으로)
vector<int> dp(1 << n, INF);
dp[0] = 0; // 기본 상태: 할당된 작업 없음
for (int mask = 0; mask < (1 << n); mask++) {
int worker = __builtin_popcount(mask); // 다음 작업자
if (worker < n) {
for (int job = 0; job < n; job++) {
if (!(mask & (1 << job))) { // 작업이 할당되지 않았다면
dp[mask | (1 << job)] = min(dp[mask | (1 << job)],
dp[mask] + cost[worker][job]);
}
}
}
}
// 정답은 dp[(1<<n)-1] - 모든 작업이 할당된 상태마스크-서브마스크 관계 (Mask-Submask Relation)
정의
- 마스크: 각 비트가 작업 할당 여부(1=할당, 0=미할당)를 나타내는 이진수
- 서브마스크: 원래 마스크의 일부 또는 모든 1 비트가 0으로 설정된 마스크
- 즉, 서브마스크는 원래 마스크에서 할당된 작업의 부분집합을 나타냄
예시
마스크 1101(작업 0, 2, 3이 할당됨)의 경우:
- 유효한 서브마스크: 0000, 0001, 0100, 1000, 0101, 1001, 1100, 1101(자기 자신)
알고리즘에서의 의미
- 마스크 M을 처리하기 전에 모든 서브마스크를 이미 처리했다는 것이 보장됨
- 이를 통해 dp[mask]는 항상 더 작은 상태의 최적 해결책을 사용하여 계산 가능
수학적 표현
- 작업 j를 현재 할당에 추가하는 경우:
- 이전 상태: dp[mask]
- 새 상태: dp[mask | (1 << j)]
- 추가로 할당하면서 원래 마스크는 새 마스크의 서브마스크가 됩니다
이터레이션 순서의 중요성
0부터 (1<<n)-1까지 마스크를 반복함으로써:
- 적은 수의 할당된 작업부터 많은 수의 할당된 작업까지 진행
- 마스크 0(이진수 000…0)을 처리할 때는 작업이 할당되지 않음
- 그다음 1비트가 설정된 마스크(한 개 작업 할당)를 처리
- 그다음 2비트가 설정된 마스크(두 개 작업 할당)를 처리
- 이런 방식으로 계속 진행되죠
- 의존성 체인 보존
- dp[mask]를 계산하기 전에, 모든 dp[submask] 값을 이미 계산한 상태
- 항상 작은 하위 문제에 대한 최적 값을 가지고 있음을 보장
이 진행 방식은 특정 상태에 도달했을 때 각 특정 상태에 대한 이전 상태 최적값은 계산을 마친 후라는 것을 보장합니다.
비트마스크 DP의 핵심은 자연스러운 이진 카운팅 시퀀스가 자동으로 하위 문제의 올바른 위상 정렬을 생성한다는 점에 있습니다.