DP on Bitmask: 비트마스크 DP

2026년 6월 29일 · 수정 2026년 6월 29일 · 📖 약 1분 · 158자/단어 #algorithm #dp #bitmask

정의

부분집합 상태를 비트마스크로 인코딩 하여 DP 를 수행. 원소 수 N ≤ 20 정도에서 유효.

자세한 내용은 DP Bitfield 참조.

dp[mask][i] = 방문한 도시 mask, 현재 i. 전이: 다음 도시 j 로 갈 때 dp[mask | (1<<j)][j] = dp[mask][i] + cost[i][j].

O(2^N · N²).

dp[i][mask] = 사람 i 까지 배정, 사용한 태스크 mask.

dp[mask][i] = mask 를 정확히 방문한 상태로 i 에서 끝나는 경로 존재 여부.

이 글의 용어 (4개)

비트마스크 DP (Bitmask DP)algorithm: 정의 비트마스크 DP (Bitmask DP) 는 상태 공간이 부분집합 으로 표현될 때, 각 부분집합을 정수의 비트로 인코딩해 DP 상태로 삼는 기법. N ≤ 20 범위에서 O(2…
Hamiltonian Path: 모든 정점 한 번씩algorithm: 정의 Hamiltonian Path 는 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로. 시작 = 끝이면 Hamiltonian Cycle. 일반 그래프에서 NP-complet…
SOS DP (Sum Over Subsets)algorithm: 정의 SOS DP (Sum Over Subsets) 는 길이 2^N 의 배열 a 에 대해, 모든 mask (0..2^N-1) 마다 mask 의 부분 집합 (submask) 에 대…
TSP (Traveling Salesman Problem): 외판원 순회algorithm: 정의 N 개 도시를 정확히 한 번씩 방문 후 시작점으로 돌아오는 최소 비용 경로. NP-hard. Bitmask DP (N ≤ 20) 상태: = "방문 집합 = mask, 현재 …