동적 계획법 (DP)

피보나치 수열을 재귀로 그대로 구하면 fib(5)를 구하려고 fib(3)을 두 번, fib(2)를 세 번 계산하는 식으로 같은 연산이 반복된다. 호출 수가 지수적으로(O(2ⁿ)) 늘어나는 이 낭비를 없애기 위해 고안된 것이 동적 계획법(Dynamic Programming) 이다.

큰 문제를 작은 문제로 나눠 풀고 그 답으로 원래 문제를 푼다는 점은 분할 정복과 같다. 차이는 하위 문제가 겹치느냐다. 동적 계획법의 하위 문제는 여러 번 반복해서 등장하므로, 한 번 구한 답을 저장해 두고 재사용한다.

적용 조건

1. 겹치는 부분 문제(Overlapping Subproblems): 같은 하위 문제가 여러 번 반복해서 등장한다. 예: 피보나치 수열
2. 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해를 하위 문제의 최적해들로 구성할 수 있다.

두 조건을 확인했다면, 문제를 하위 문제로 나누는 점화식을 세우는 것이 핵심이다. 피보나치라면 F(n) = F(n-1) + F(n-2).

Top-Down: 메모이제이션 (Memoization)

큰 문제에서 시작해 재귀로 내려가면서, 이미 계산한 하위 문제는 저장해 둔 값을 바로 꺼내 쓴다. 같은 하위 문제의 답은 언제 구해도 같으므로 캐시에 메모해 두는 것이다.

memo = [0] * 100
memo[0] = memo[1] = 1      # 이 노트에서는 F(0) = F(1) = 1로 둔다
 
def fib_memo(n):
    if memo[n] == 0:                               # 아직 계산하지 않았다면
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2) # 자기 자신을 재귀 호출
    return memo[n]
 
print(fib_memo(10))  # 89

메모 함수 안에서 메모이제이션이 없는 다른 함수를 호출하면 캐시 효과가 사라진다. 재귀 호출은 반드시 자기 자신(fib_memo)을 부른다.

파이썬에서는 데코레이터로 더 간단히 쓸 수 있다.

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Bottom-Up: 타뷸레이션 (Tabulation)

가장 작은 하위 문제부터 차례로 표(DP 테이블)를 채워 올라간다. 재귀가 없어 재귀 깊이 제한에 걸리지 않고, 보통 더 빠르다.

def fib_tab(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)              # n = 0이면 dp[1]이 없으므로 위에서 먼저 처리
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
 
print(fib_tab(10))  # 89

직전 두 값만 필요하므로 변수 두 개로 공간을 O(1)까지 줄일 수도 있다.

def fib_tab2(n):
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

2차원 DP도 같다. dp[i][j]가 바로 윗줄 dp[i-1][…]만 참조하면 표 전체 대신 두 줄(이전 줄과 현재 줄)만 들고 번갈아 쓰면 공간이 O(nm)에서 O(m)으로 준다. 0/1 배낭처럼 같은 줄을 뒤에서부터 갱신하면 한 줄로도 된다. 다만 줄인 표에서는 지나간 상태가 지워지므로, 최적해 자체(어떤 원소를 골랐나)를 복원해야 하면 전체 표를 남긴다.

두 방식 모두 피보나치를 O(n)에 구한다.

DP 문제에 접근하는 순서

1. 이 문제가 최적성의 원리(부분 문제의 최적해가 전체 최적해를 만드는 데 쓰이는가)를 만족하는지 판단한다.
2. dp[i]가 무엇을 의미하는지 정의한다.
3. 점화식을 세운다.
4. 초기값(기저 사례)을 정한다.
5. Top-Down 또는 Bottom-Up으로 구현한다.

점화식이 바로 안 보이면 재귀(Top-Down)로 먼저 짠다. "이 문제를 풀려면 어떤 더 작은 문제의 답이 필요한가"를 그대로 함수 호출로 옮기면 되고, 반복문 버전은 그 호출 순서를 뒤집기만 하면 된다.

하위 문제를 찾는 연습

점화식을 찾는 공식은 없다. 대신 마지막 한 단계에서 무엇을 하는가를 묻는 습관이 도움이 된다.

타일 문제에서 11을 길이 2 타일로 따로 세지 않는 이유는 1을 두 번 붙인 경우와 겹치기 때문이다. 하위 문제는 겹치지 않고 빠짐없이 나눠야 한다. 하위 문제의 단위는 숫자 하나일 수도, 문자열의 앞부분, 격자의 일부, 그래프의 정점일 수도 있다. 단위를 어떻게 잡느냐에 따라 dp 배열의 모양과 풀이 성패가 갈린다.

타일링처럼 답이 큰 문제는 보통 1,000,000,007 같은 큰 소수로 나눈 나머지를 요구한다. 덧셈할 때마다 나머지를 취해 오버플로를 막는다. n이 수만 이상이면 Top-Down 재귀는 호출 스택 한도에 걸린다(파이썬 기본 1000, JavaScript는 엔진 설정에 따라 약 1만 단위에서 Maximum call stack size exceeded). 이럴 때는 Bottom-Up으로 쓴다.

구간 DP: 연쇄 행렬 곱셈

하위 문제가 "앞부분"이 아니라 구간 [i, j]인 DP도 있다. 대표 예가 연쇄 행렬 곱셈(matrix chain multiplication)이다. a×b 행렬과 b×c 행렬의 곱은 곱셈 a·b·c번이 들고, 행렬 여러 개를 곱할 때는 결과가 같아도 괄호를 치는 순서에 따라 비용이 크게 달라진다. 5×3, 3×10, 10×6이면 (AB)C는 150 + 300 = 450번, A(BC)는 180 + 90 = 270번이다.

M[i][j] = i번째부터 j번째 행렬까지 곱하는 최소 비용   (행렬 i의 크기 d[i-1] × d[i])
M[i][i] = 0
M[i][j] = min over i ≤ k < j of  M[i][k] + M[k+1][j] + d[i-1]·d[k]·d[j]

마지막에 곱하는 경계 k를 모두 시도하는 것이 핵심이다. 구간 길이가 짧은 것부터 채워야 필요한 값이 미리 준비된다. 테이블의 대각선부터 오른쪽 위로 한 줄씩 채우는 셈이다.

def matrix_chain(sizes):             # sizes = [(r1, c1), (r2, c2), ...]
    n = len(sizes)
    dp = [[0] * n for _ in range(n)]
    for length in range(1, n):       # 구간 길이 - 1
        for i in range(n - length):
            j = i + length
            dp[i][j] = min(dp[i][k] + dp[k + 1][j] + sizes[i][0] * sizes[k][1] * sizes[j][1]
                           for k in range(i, j))
    return dp[0][n - 1]
 
print(matrix_chain([(5, 3), (3, 10), (10, 6)]))  # 270

상태가 O(n²)개이고 상태마다 k를 O(n)개 시도하므로 O(n³)이다. 파일 합치기, 팰린드롬 분할, 최적 이진 탐색 트리도 같은 구간 DP 틀이다.

다른 기법과 비교

세 기법은 모두 큰 문제를 작은 문제로 줄여 풀지만, 하위 문제가 겹치는가와 선택을 되돌아보는가로 갈린다.

피보나치처럼 한 하위 문제의 답이 여러 상위 문제에 쓰이면 DP, 병합 정렬처럼 나뉜 부분이 서로 영향을 주지 않으면 분할 정복이다. 그리디로 풀리는지 확신이 없으면 DP로 푸는 쪽이 안전하다.

핵심 정리

• DP = 겹치는 부분 문제 + 최적 부분 구조, 답을 저장해 재사용
• Top-Down(메모이제이션, 재귀)과 Bottom-Up(타뷸레이션, 반복문) 두 방식
• 핵심은 dp[i]의 정의와 점화식

관련 노트: 재귀 함수, 분할 정복, 그리디, 최장 증가 부분 수열, 선형 점화식의 일반항