[DP-4] 구간 DP & 비트마스크 DP

카테고리 없음

[DP-4] 구간 DP & 비트마스크 DP

the.Dev.Cat 2026. 5. 12. 07:34

구간 DP & 비트마스크 DP — 알고리즘 스터디 9주차

Python 코딩테스트 알고리즘 스터디 9주차 — 동적 계획법(DP) 내용을 정리한 글이다.

구간에 대한 최적값 탐색과 집합 상태를 정수 하나로 압축하는 기법

1. 구간 DP

구간 DP는 배열의 연속된 구간 [i, j]를 대상으로 하는 DP다. dp[i][j]는 구간 i부터 j까지에 대한 최적값을 저장한다.

구간 DP의 일반적인 구조:

길이가 1인 구간부터 시작한다.
구간 길이를 늘려가며 탐색한다.
각 구간을 어느 지점 k에서 분할할지 결정한다.

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        for k in range(i, j):
            dp[i][j] = optimal(dp[i][k], dp[k + 1][j])

구간 DP 순회 순서가 중요한 이유

짧은 구간의 최적값이 먼저 채워져야 긴 구간을 올바르게 계산할 수 있다. for length in range(2, n+1)로 구간 길이 순서로 순회하면 이 조건이 자동으로 충족된다.

팰린드롬 분할

문자열 S가 주어질 때, S를 팰린드롬으로만 구성된 부분 문자열로 자르는 최소 횟수를 구하는 문제다.

is_palindrome[i][j]	S[i..j]가 팰린드롬인지 여부
cut[i]	S[0..i]를 팰린드롬으로 분할하는 최소 횟수

def min_palindrome_cut(s):
    n = len(s)
    is_palindrome = [[False] * n for _ in range(n)]

    for i in range(n):
        is_palindrome[i][i] = True

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 2:
                is_palindrome[i][j] = (s[i] == s[j])
            else:
                is_palindrome[i][j] = (s[i] == s[j] and is_palindrome[i + 1][j - 1])

    cut = list(range(n))

    for i in range(1, n):
        if is_palindrome[0][i]:
            cut[i] = 0
            continue
        for j in range(1, i + 1):
            if is_palindrome[j][i]:
                cut[i] = min(cut[i], cut[j - 1] + 1)

    return cut[n - 1]

print(min_palindrome_cut("aab"))
print(min_palindrome_cut("abcbc"))

1
1

"aab" → "aa" | "b": 1번 분할. "abcbc" → "a" | "bcb" | "c": 2번이 아니라, 전체 구간을 점검해 최솟값이 1임을 확인한다.

행렬 연쇄 곱셈

행렬 A(p×q)와 B(q×r)의 곱셈에는 p×q×r번의 연산이 필요하다. 행렬 여러 개를 곱할 때 순서에 따라 연산 횟수가 크게 달라진다. 어떤 순서로 곱해야 최소 연산 횟수가 되는지 구하는 문제다.

dp[i][j]의 의미	i번째부터 j번째 행렬을 곱하는 최소 연산 횟수
점화식	dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1])

def matrix_chain_order(dims):
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')

            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

dims = [10, 30, 5, 60]
print(matrix_chain_order(dims))

4500

A(10×30), B(30×5), C(5×60)을 곱할 때: (AB)C = 10×30×5 + 10×5×60 = 1500 + 3000 = 4500, A(BC) = 30×5×60 + 10×30×60 = 27000. 최소는 4500이다.

2. 비트마스크 DP

비트마스크로 상태 표현하기

비트마스크는 집합을 정수로 표현하는 방법이다. n개의 원소가 있을 때 각 원소의 포함 여부를 비트 하나로 나타낸다.

  원소: [A, B, C, D]

  비트:  3  2  1  0

  0b0000 = 0  : {}

  0b0001 = 1  : {A}

  0b0011 = 3  : {A, B}

  0b1010 = 10 : {B, D}

  0b1111 = 15 : {A, B, C, D}

비트 상태 시각화 — visited = 0b1010 (B, D 방문)

비트3 D (1)

비트2 C (0)

비트1 B (1)

비트0 A (0)

어두운 칸 = 비트 1 (방문), 보라 칸 = 비트 0 (미방문). 위 예시에서 visited = 0b1010 = 10

비트 연산으로 집합 연산을 O(1)에 수행할 수 있다.

연산	코드	의미
원소 i 추가	`state \| (1 << i)`	i번 비트를 1로 설정
원소 i 제거	`state & ~(1 << i)`	i번 비트를 0으로 설정
원소 i 포함 여부	`state & (1 << i)`	i번 비트가 1인지 확인
전체 집합	`(1 << n) - 1`	n개 비트 모두 1

visited = 0b0000

visited |= (1 << 0)
print(bin(visited))

visited |= (1 << 2)
print(bin(visited))

print(bool(visited & (1 << 2)))
print(bool(visited & (1 << 1)))

0b1
0b101
True
False

외판원 문제 (TSP)

n개의 도시를 모두 방문하고 출발 도시로 돌아오는 최소 비용 경로를 구하는 문제다. 완전 탐색으로는 O(n!)이지만, 비트마스크 DP로 O(2^n × n²)으로 줄일 수 있다.

dp[visited][i]의 의미	방문한 도시 집합이 visited이고 현재 도시가 i일 때, 아직 방문하지 않은 도시를 모두 방문하고 출발지로 돌아오는 최소 비용
초기값	dp[1][0] = 0 (도시 0에서 출발, 방문 집합에 도시 0만 포함)

TSP 비트 상태 다이어그램 — 4개 도시

dp[1][0] = 0 에서 출발 (도시 0만 방문)

visited=0001

도시0 (현재)

도시1

도시2

도시3

visited=0011

도시0 (방문)

도시1 (현재)

도시2

도시3

visited=1111

도시0 (방문)

도시1 (방문)

도시2 (방문)

도시3 (현재)

보라 = 현재 위치, 어두운 = 이미 방문, 회색 글씨 = 미방문

import sys

def tsp(dist):
    n = len(dist)
    INF = sys.maxsize
    full = (1 << n) - 1
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0

    for visited in range(1 << n):
        for curr in range(n):
            if dp[visited][curr] == INF:
                continue
            if not (visited & (1 << curr)):
                continue

            for next_city in range(n):
                if visited & (1 << next_city):
                    continue
                if dist[curr][next_city] == 0:
                    continue

                next_visited = visited | (1 << next_city)
                new_cost = dp[visited][curr] + dist[curr][next_city]

                if dp[next_visited][next_city] > new_cost:
                    dp[next_visited][next_city] = new_cost

    result = INF
    for last in range(1, n):
        if dist[last][0] > 0 and dp[full][last] != INF:
            result = min(result, dp[full][last] + dist[last][0])

    return result

dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(tsp(dist))

80

0→1→3→2→0: 10+25+30+15 = 80. TSP는 n이 20 이하일 때 비트마스크 DP가 적합하다. n이 크면 2^n이 너무 커진다.

3. 시간 복잡도

유형	시간 복잡도	공간 복잡도	비고
LCS	O(m × n)	O(m × n)	m, n: 두 문자열 길이
편집 거리	O(m × n)	O(m × n)	1차원 최적화 가능
0/1 배낭	O(n × W)	O(n × W) → O(W)	1차원 배열로 최적화
팰린드롬 DP	O(n²)	O(n²)
행렬 연쇄 곱셈	O(n³)	O(n²)
TSP (비트마스크)	O(2^n × n²)	O(2^n × n)	n ≤ 20 실용적

4. 유형별 접근 전략

2차원 DP 중 어떤 방식을 써야 하는지 판별하는 기준이다.

두 개의 입력 시퀀스가 동시에 관계를 맺는 경우

두 문자열, 두 배열이 주어지고 공통 요소를 찾거나 변환 비용을 계산해야 한다. LCS, 편집 거리가 해당된다.

하나의 입력에 두 가지 제약이 동시에 있는 경우

물건 개수와 무게 용량처럼 두 개의 변수가 독립적으로 상태를 구성한다. 배낭 문제가 해당된다.

구간 [i, j]에 대한 최적해를 구해야 하는 경우

배열의 부분 구간을 분할하거나 구성하는 방식을 선택해야 한다. 행렬 연쇄 곱셈, 팰린드롬 분할이 해당된다.

방문 상태를 집합으로 표현해야 하는 경우

노드를 모두 방문해야 하는 최적화 문제에서 상태 수가 2^n으로 제한될 때 비트마스크 DP를 쓴다. TSP가 대표적이다.

2차원 DP에서 가장 중요한 것은 여전히 상태 정의다. dp[i][j]가 무엇을 의미하는지 명확히 설정하지 않으면 점화식을 세울 수 없다. 상태 정의 후 점화식이 더 작은 인덱스만 참조하는지, 초기값이 명확한지, 계산 순서가 올바른지 점검해야 한다.

5. Python 자주 쓰는 메서드

구간 DP 순회 패턴

n = 5
dp = [[0] * n for _ in range(n)]

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        print(f"구간 [{i}, {j}]  (길이 {length})")

구간 [0, 1]  (길이 2)
구간 [1, 2]  (길이 2)
구간 [2, 3]  (길이 2)
구간 [3, 4]  (길이 2)
구간 [0, 2]  (길이 3)
구간 [1, 3]  (길이 3)
구간 [2, 4]  (길이 3)
구간 [0, 3]  (길이 4)
구간 [1, 4]  (길이 4)
구간 [0, 4]  (길이 5)

for length in range(2, n+1): 구간 길이 순서로 순회
for i in range(n - length + 1): 시작점 순회
j = i + length - 1: 끝점 계산

비트마스크 기본 연산

n = 4
mask = 0

mask = mask | (1 << 1)
print(f"1번 비트 설정: {bin(mask)}")

mask = mask | (1 << 3)
print(f"3번 비트 설정: {bin(mask)}")

print(f"1번 비트 확인: {bool(mask & (1 << 1))}")
print(f"2번 비트 확인: {bool(mask & (1 << 2))}")

mask = mask ^ (1 << 1)
print(f"1번 비트 토글: {bin(mask)}")

full = (1 << n) - 1
print(f"전체 방문 상태: {bin(full)}")

1번 비트 설정: 0b10
3번 비트 설정: 0b1010
1번 비트 확인: True
2번 비트 확인: False
1번 비트 토글: 0b1000
전체 방문 상태: 0b1111

연산	코드	설명
i번째 비트 마스크 생성	`1 << i`	i번 비트만 1인 정수
i번째 비트 설정	`mask \| (1 << i)`	i번 비트를 1로
i번째 비트 확인	`mask & (1 << i)`	결과가 0이면 미설정
i번째 비트 토글	`mask ^ (1 << i)`	0이면 1로, 1이면 0으로
전체 방문 상태	`(1 << n) - 1`	n개 비트 모두 1

bin() — 비트 상태 디버깅

states = [0, 1, 5, 10, 15]
for s in states:
    print(f"{s:3d} → {bin(s):>8s} → {bin(s)[2:].zfill(4)}")

→    0b0 → 0000
→    0b1 → 0001
→  0b101 → 0101
→ 0b1010 → 1010
→ 0b1111 → 1111

bin(mask)는 비트마스크 DP 디버깅 시 현재 방문 상태를 시각적으로 확인하는 데 유용하다. [2:]로 0b 접두사를 제거하고 zfill(n)으로 자릿수를 맞출 수 있다.

(1 << n) - 1 — 전체 방문 상태

for n in range(1, 6):
    full = (1 << n) - 1
    print(f"n={n}: full={full} ({bin(full)})")

n=1: full=1 (0b1)
n=2: full=3 (0b11)
n=3: full=7 (0b111)
n=4: full=15 (0b1111)
n=5: full=31 (0b11111)

TSP처럼 모든 노드를 방문했는지 확인할 때 visited == (1 << n) - 1 조건으로 판단한다.

6. 연습 문제

초급

번호	문제	난이도	핵심 접근
87946	피로도	Lv.2	비트마스크 완전 탐색, 모든 방문 순서 중 최대 던전 수 탐색
43164	여행경로	Lv.3	DFS + 경로 추적, 모든 항공권 사용하는 알파벳 순 최소 경로

중급

번호	문제	난이도	핵심 접근
42895	N으로 표현	Lv.3	사용 횟수별 만들 수 있는 수 집합 DP, 집합 합집합으로 상태 갱신
42898	등굣길	Lv.3	격자 이동 DP, dp[i][j] = dp[i-1][j] + dp[i][j-1] (장애물 처리 포함)