비트마스크 DP (Bitmask Dynamic Programming)

비트마스크 DP (Bitmask Dynamic Programming)

집합의 상태를 비트마스크로 표현하여 부분집합을 효율적으로 관리하는 동적 프로그래밍 기법으로, 원소 개수 N이 작을 때(보통 20 이하) 2^N 상태 공간 탐색

목적: 부분집합 상태 관리, 지수 시간 문제의 효율화, TSP 해결

특징: 비트로 집합 표현, 2^N 상태, O(N * 2^N) 또는 O(N^2 * 2^N), 메모이제이션

비트마스크 표현

• •집합 {0, 2, 3} → 1101(2) = 13
• •i번째 원소 포함 여부: (mask >> i) & 1
• •i번째 원소 추가: mask | (1 << i)
• •i번째 원소 제거: mask & ~(1 << i)

대표 문제: TSP(외판원 문제)

• •dp[mask][i] = mask 집합의 도시를 방문하고 현재 i에 있을 때 최소 비용
• •점화식: dp[mask][i] = min(dp[mask^(1<
• •시간 복잡도: O(N^2 * 2^N)

부분집합 열거

• •모든 부분집합: for(s=mask; s>0; s=(s-1)&mask)
• •원소 하나씩: for(i=0; i

적용 조건: N ≤ 20 (2^20 ≈ 100만), 상태 전이 명확, 부분문제 중복

장점: 집합 연산 O(1), 상태 표현 간결, 완전 탐색보다 효율

단점: N 제한(20~25), 지수 복잡도, 메모리 사용

적용사례: TSP, 할당 문제, 해밀턴 경로, 게임 이론, 스케줄링

비교: 비트마스크DP(2^N/작은N) vs 완전탐색(N!/비효율) vs 근사알고리즘(다항/근사)

연관: DP, TSP, 비트 연산, 부분집합, 조합 최적화