N개의 도시를 전부 방문하는 최소 비용을 구하라. 직원 N명에게 업무 N개를 1:1로 배정하는 최적 조합을 찾아라. 처음 보면 "경우의 수가 폭발하는데 이걸 어떻게?" 싶은 문제들이 있다. 비트마스크 DP는 그 폭발을 제어 가능한 범위로 끌어내린다.

부분집합을 정수 하나로 표현한다

원소가 5개인 집합 {0, 1, 2, 3, 4}에서 {0, 2, 3}이라는 부분집합을 생각해 보자. 각 원소의 포함 여부를 비트로 나타내면 01101 → 정수 13이다. 포함되면 1, 아니면 0. 이렇게 하면 N개 원소의 모든 부분집합이 0부터 2^N − 1까지의 정수와 1:1 대응된다.

핵심은 집합 연산이 비트 연산 한 줄로 끝난다는 점이다.

연산 의미 코드
state | (1 << i) 원소 i 추가 OR
state & (1 << i) 원소 i 포함 여부 확인 AND
state & ~(1 << i) 원소 i 제거 AND NOT
state ^ (1 << i) 원소 i 토글 XOR

배열이나 set으로 부분집합을 관리하면 복사·비교에 O(N)이 드는데, 정수 하나면 O(1)이다. DP 테이블의 인덱스로 바로 쓸 수 있다는 게 진짜 강점. dp[visited] 형태로 "어떤 원소들을 이미 처리했는지"를 상태 하나에 담는다.

TSP로 감 잡기

외판원 문제(Traveling Salesman Problem)가 비트마스크 DP의 교과서적 예제다. N개 도시를 한 번씩 전부 방문하고 출발점으로 돌아올 때의 최소 비용을 구하는 문제. 완전 탐색이면 O(N!) — N=15일 때 이미 1조를 넘는다.

비트마스크 DP로 뒤집으면 dp[visited][cur]. visited는 지금까지 방문한 도시 집합을 비트로 압축한 정수, cur은 현재 위치.

def tsp(n, dist):
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 0번 도시에서 출발, 방문 표시

    for visited in range(1 << n):
        for cur in range(n):
            if dp[visited][cur] == INF:
                continue
            for nxt in range(n):
                if visited & (1 << nxt):
                    continue
                new_v = visited | (1 << nxt)
                dp[new_v][nxt] = min(dp[new_v][nxt],
                                     dp[visited][cur] + dist[cur][nxt])

    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

시간복잡도 O(2^N × N²). N=20이면 약 4억 연산으로 빡빡하지만 돌아간다. 팩토리얼 O(N!)은 같은 N에서 2.4 × 10^18이니까, 비교 자체가 의미 없는 격차다.

코테에서 마주치는 변형 패턴

TSP가 그대로 나오는 경우는 드물다. 시험장에서는 "집합을 정수로 압축한다"는 아이디어를 변형해서 출제한다. 자주 보이는 세 가지.

업무 배정(할당) 문제. N명에게 N개 업무를 1:1 배정할 때 최소 비용. dp[mask]를 "mask에 해당하는 업무들이 이미 배정된 상태에서의 최소 비용"으로 정의한다. 몇 번째 사람까지 배정했는지는 mask에서 켜진 비트 수(popcount)로 자동 결정되니까 별도 차원이 필요 없다. 헝가리안 알고리즘보다 구현이 훨씬 직관적이고, N ≤ 20이면 속도도 충분하다.

체크포인트 BFS. 최단 경로를 구해야 하는데, 특정 지점들을 반드시 거쳐야 하는 제약이 붙는 문제. 일반 BFS는 "어떤 체크포인트를 이미 지났는지" 추적이 안 된다. 상태를 (위치, 방문한 체크포인트 비트마스크)로 확장하면 해결된다. 체크포인트가 10개 이하면 넉넉히 돌아간다.

부분집합의 부분집합 열거. 특정 비트마스크 state의 모든 부분집합을 빠르게 도는 테크닉이 있다:

sub = state
while sub:
    process(sub)
    sub = (sub - 1) & state

이 3줄을 모르면 매번 부분집합을 직접 생성해야 해서 시간 초과의 원인이 된다. 집합 분할 DP 같은 문제에서 꽤 자주 등장하는 패턴이니 반드시 익혀두자.

자주 하는 실수 모음

비트마스크 DP를 처음 짜면 한두 번은 반드시 당하는 것들이다.

  • 0-indexed / 1-indexed 혼동. 도시 번호가 1부터인데 비트는 0부터 세면 한 칸씩 밀린다. 입력 시점에 통일하자.

  • C++/Java에서 1 << i 오버플로. i ≥ 31이면 int 범위를 넘긴다. 반드시 1L << i로 long 캐스팅.

  • 초기 상태 누락. TSP에서 dp[1][0] = 0을 빼먹으면 전부 INF인 채로 끝난다. 출발점을 visited에 표시하는 걸 놓치는 실수가 정말 많다.

  • 메모리 초과. 2^20 × 20 × 4바이트 ≈ 80MB. 문제의 메모리 제한이 256MB인지 512MB인지 꼭 확인하고, 타이트하면 차원 축소나 rolling 기법을 고려해야 한다.

비트마스크를 떠올리는 기준

시험장에서 "이거 비트마스크다"를 빠르게 감지하는 게 실력이다. 신호는 꽤 명확한 편인데, N이 20 이하이면서 부분집합 또는 순열이 상태에 관여하는 문제가 핵심 조건이다. "모든 도시를 방문", "모든 업무를 배정", "특정 포인트를 전부 거쳐야" 같은 키워드가 보이면 비트마스크부터 설계해보자.

반대로 N이 크면? 비트마스크는 포기하고 그리디, 세그먼트 트리, 네트워크 플로우 같은 다른 무기를 꺼내야 한다. 2^N은 자비가 없다.

연습 추천 문제: 백준 2098(외판원 순회), 1102(발전소), 11723(집합), 프로그래머스 "외벽 점검". 3~4문제만 직접 짜보면 비트 연산이 손에 붙기 시작한다. 비트마스크 DP는 이해했다고 끝이 아니라 손이 기억해야 쓸 수 있는 유형이다.