Skip to content

Latest commit

 

History

History
686 lines (484 loc) · 30.8 KB

Concepts_Lecture.ko.md

File metadata and controls

686 lines (484 loc) · 30.8 KB

6주차 이론 — 동적 프로그래밍

레포지토리 안내 | English | 한국어

최종 수정일: 2026-11-18

Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, Ch 15, 25

학습 목표:

  1. 동적 프로그래밍을 정의하고, DP에 필요한 두 가지 성질(최적 부분 구조, 중복 부분 문제)을 기술할 수 있다
  2. DP와 분할 정복을 구별하고, 각각 언제 적합한지 설명할 수 있다
  3. 하향식(메모이제이션)과 상향식(테이블화) DP 전략을 모두 구현할 수 있다
  4. 피보나치, 행렬 경로, LCS, 0-1 배낭, 동전 거스름돈, 플로이드-워셜, 편집 거리 문제를 DP로 풀 수 있다
  5. DP 점화식을 공식화(부분 문제 정의, 기저 사례 식별, 계산 순서 결정)하고 DP 알고리즘의 시간 및 공간 복잡도를 분석할 수 있다
  6. DP와 그리디 알고리즘을 비교하고, 주어진 문제에 어떤 접근법을 사용할지 결정할 수 있다

목차



1. 동적 프로그래밍의 기초

1.1 재귀적 풀이: 빛과 그림자

재귀가 잘 작동하는 경우:

  • 부분 문제 입력의 합이 원래 입력 크기 이하이다.
  • 병합 정렬, 퀵 정렬, 팩토리얼, 그래프 DFS가 이에 해당한다.

재귀가 치명적인 경우:

  • 부분 문제 입력의 합이 원래 입력보다 크다.
  • 피보나치 수, 행렬 체인 곱셈이 이에 해당한다.

핵심: 중복 부분 문제(overlapping subproblems) 가 지수적인 중복 계산을 유발한다.

1.2 동적 프로그래밍의 개념

동적 프로그래밍(DP) 은 다음과 같이 중복 계산을 피한다.

  1. 작은 부분 문제를 먼저 푼다.
  2. 그 해를 저장(기억)한다.
  3. 저장된 해를 사용하여 더 큰 부분 문제를 푼다.
  4. 원래 문제까지 쌓아 올린다.

DP의 두 가지 요건:

성질 설명
최적 부분 구조 최적해가 부분 문제의 최적해를 포함한다
중복 부분 문제 재귀적 풀이가 같은 부분 문제를 반복적으로 다시 푼다

표 1. DP의 두 가지 요건

핵심: DP는 각 부분 문제를 정확히 한 번만 풀므로, 서로 다른 부분 문제의 수가 다항식 개이면 지수 시간 재귀 알고리즘을 다항 시간 알고리즘으로 바꾼다. 동적 프로그래밍의 "프로그래밍"은 컴퓨터 프로그래밍이 아니라 테이블 방식(tabular method)을 의미한다.

최적 부분 구조가 없는 문제의 예로 가중치 없는 방향 그래프의 최장 단순 경로 문제가 있다. 그림 1에서 q에서 t까지의 최장 단순 경로 중 하나는 q → r → t이지만, 그 부분 경로 q → r은 q에서 r까지의 최장 단순 경로(q → s → t → r)가 아니다. 따라서 부분 문제의 최적해를 이어 붙여 전체 최적해를 만들 수 없다.

그림 1. 최장 단순 경로 문제에 최적 부분 구조가 없음을 보이는 방향 그래프

그림 1. 최장 단순 경로 문제에 최적 부분 구조가 없음을 보이는 방향 그래프

1.3 DP vs 분할 정복

graph TD
    subgraph dc["분할 정복"]
        a1["A"] --> b1["B"]
        a1 --> c1["C"]
        b1 --> d1["D"]
        b1 --> e1["E"]
        c1 --> f1["F"]
        c1 --> g1["G"]
    end
    subgraph dp["DP"]
        a2["A"] --> b2["B"]
        a2 --> c2["C"]
        b2 --> d2["D"]
        b2 --> e2["E (공유)"]
        b2 --> f2["F (공유)"]
        c2 --> e2
        c2 --> f2
        c2 --> g2["G"]
    end
Loading

그림 2. 분할 정복의 독립 부분 문제와 DP의 공유 부분 문제

  • 분할 정복에서는 부분 문제가 독립적이어서 각각 한 번씩 풀린다.
  • DP에서는 부분 문제가 중복되므로 한 번 풀어 저장하고 재사용한다.
  • 분할 정복은 하향식으로 문제를 나누고, DP는 보통 작은 것에서 큰 것으로 상향식으로 계산한다(1.4절의 메모이제이션처럼 하향식으로도 구현할 수 있다).

분할 정복에서 재귀 호출 트리는 트리(반복 노드 없음)이지만, DP에서 부분 문제 의존성은 공유 노드가 있는 DAG(방향 비순환 그래프)를 형성한다. 그림 3은 크기 4인 문제를 크기 3, 2, 1, 0인 부분 문제로 나누는 재귀를 그대로 실행했을 때의 호출 트리로, 같은 부분 문제가 반복해서 나타난다(크기 2는 2번, 크기 1은 4번, 크기 0은 8번). 그림 4는 같은 부분 문제를 한 번씩만 두고 의존 관계를 간선으로 나타낸 DAG이다.

그림 3. 크기 4인 문제를 그대로 재귀 호출할 때의 호출 트리

그림 3. 크기 4인 문제를 그대로 재귀 호출할 때의 호출 트리

그림 4. 크기 4인 문제의 부분 문제 DAG

그림 4. 크기 4인 문제의 부분 문제 DAG

1.4 두 가지 DP 구현 전략

하향식: 메모이제이션 (Memoization)

  • 재귀를 사용하되 결과를 테이블에 캐시한다.
  • 실제로 필요한 부분 문제만 푼다.

상향식: 테이블화 (Tabulation)

  • 가장 작은 부분 문제부터 반복적으로 테이블을 채운다.
  • 모든 부분 문제를 순서대로 푸는 체계적인 방식이다.
하향식 (메모이제이션)                상향식 (테이블화)
┌──────────────────────┐        ┌──────────────────────┐
│ fib(n):              │        │ f[1] = f[2] = 1      │
│   if memo[n] exists  │        │ for i = 3 to n:      │
│     return memo[n]   │        │   f[i] = f[i-1]      │
│   memo[n] = fib(n-1) │        │        + f[i-2]      │
│            +fib(n-2) │        │ return f[n]          │
│   return memo[n]     │        │                      │
└──────────────────────┘        └──────────────────────┘

참고: 상황별 선택. 메모이제이션은 구현이 더 쉽고(재귀에 캐싱만 추가) 불필요한 부분 문제 풀이를 피한다. 테이블화는 재귀 오버헤드를 피하며 실제로는 보통 더 빠르다. 대부분의 DP 문제는 어느 쪽으로든 풀 수 있다.

1.5 예제: 피보나치 수

피보나치 수는 $f(1) = f(2) = 1$이고 $n \geq 3$이면 $f(n) = f(n-1) + f(n-2)$인 수열로 정의된다.

순진한 재귀:

fib(n):
    if n = 1 or n = 2: return 1
    return fib(n-1) + fib(n-2)

fib(7)의 호출 트리: 중복 계산이 매우 많다.

graph TD
    f7["fib(7)"] --> f6["fib(6)"]
    f7 --> f5a["fib(5)"]
    f6 --> f5b["fib(5)"]
    f6 --> f4a["fib(4)"]
    f5a --> f4b["fib(4)"]
    f5a --> f3["fib(3)"]
    f5b --> e1["..."]
    f4a --> e2["..."]
    f4b --> e3["..."]
    f3 --> e4["..."]
Loading

그림 5. 순진한 재귀로 fib(7)을 계산할 때의 호출 트리

fib(5)는 두 번, fib(4)는 3번, fib(3)은 5번 계산된다.

시간 복잡도: 지수 시간인 $O(2^n)$이다.

1.6 피보나치: 메모이제이션 vs 상향식 DP

메모이제이션 (하향식):

f[1] = f[2] = 1; 나머지 모두 = 0

fib(n):
    if f[n] != 0: return f[n]
    f[n] = fib(n-1) + fib(n-2)
    return f[n]

상향식 DP (테이블화):

fibonacci(n):
    f[1] = f[2] = 1
    for i = 3 to n:
        f[i] = f[i-1] + f[i-2]
    return f[n]
i 1 2 3 4 5 6 7
f[i] 1 1 2 3 5 8 13

표 2. 상향식 DP로 채운 피보나치 테이블 f

둘 다 O(n) 시간을 달성하여, 지수 시간이 선형 시간으로 줄어든다.

1.7 예제: 행렬 경로 문제

문제: $n \times n$ 양의 정수 행렬이 주어졌을 때, 좌상단 $(1,1)$에서 우하단 $(n,n)$까지 방문 셀의 합을 최대화하는 경로를 구하라.

제약 조건: 오른쪽 또는 아래로만 이동할 수 있다(왼쪽, 위, 대각선으로는 이동할 수 없다).

┌────┬────┬────┬────┐
│  6 │  7 │ 12 │  5 │
├────┼────┼────┼────┤
│  5 │  3 │ 11 │ 18 │
├────┼────┼────┼────┤
│  7 │ 17 │  3 │  3 │
├────┼────┼────┼────┤
│  8 │ 10 │ 14 │  9 │
└────┴────┴────┴────┘

그림 6. 4 × 4 행렬 경로 문제의 입력 행렬

점화식: $c[i, j] = m_{ij} + \max(c[i-1, j],\ c[i, j-1])$

경계 조건: $c[i, 0] = c[0, j] = 0$

참고: 최적 부분 구조. 셀 $(i,j)$까지의 최적 경로는 반드시 위쪽 셀 $(i-1,j)$ 또는 왼쪽 셀 $(i,j-1)$ 중 누적 합이 더 큰 쪽에서 도착해야 한다.

1.8 행렬 경로: DP 테이블

matrixPath(n):
    for i = 0 to n: c[i, 0] = 0
    for j = 1 to n: c[0, j] = 0
    for i = 1 to n:
        for j = 1 to n:
            c[i, j] = m[i,j] + max(c[i-1, j], c[i, j-1])
    return c[n, n]
c 0 1 2 3 4
0 0 0 0 0 0
1 0 6 13 25 30
2 0 11 16 36 54
3 0 18 35 39 57
4 0 26 45 59 68

표 3. 행렬 경로 문제의 DP 테이블 c

정답: $c[4, 4] = 68$. 시간: $O(n^2)$.



2. 고전적인 DP 문제

2.1 LCS: 문제 정의

최장 공통 부분 수열 (Longest Common Subsequence, LCS)

  • 부분 수열(subsequence) 은 나머지 문자의 순서를 바꾸지 않고 0개 이상의 문자를 삭제하여 얻는다.
  • X와 Y의 공통 부분 수열은 두 문자열 모두에 나타나는 부분 수열이다.
  • LCS는 그러한 공통 부분 수열 중 가장 긴 것이다.

예시:

  • X = ABCBDAB, Y = BDCABA
  • 공통 부분 수열: BCA (길이 3)
  • LCS: BCBA (길이 4)

목표: LCS의 길이를 구하라 (선택적으로 수열 자체도).

2.2 LCS: 점화식

$X_m = \langle x_1, x_2, \ldots, x_m \rangle$과 $Y_n = \langle y_1, y_2, \ldots, y_n \rangle$으로 놓는다.

$c[i, j]$ = $X_i$와 $Y_j$의 LCS 길이로 정의한다.

$$c[i, j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\\ c[i-1, j-1] + 1 & \text{if } i,j > 0 \text{ and } x_i = y_j \\\ \max(c[i-1, j],\ c[i, j-1]) & \text{if } i,j > 0 \text{ and } x_i \neq y_j \end{cases}$$

직관:

  • 마지막 문자가 일치하면 더 짧은 접두사의 LCS를 1 확장한다.
  • 일치하지 않으면 어느 한 문자를 뺀 두 경우 중 더 나은 결과를 취한다.

2.3 LCS: 의사코드

LCS(m, n):
    for i = 0 to m: C[i, 0] = 0    // Y가 빈 경우
    for j = 0 to n: C[0, j] = 0    // X가 빈 경우
    for i = 1 to m:
        for j = 1 to n:
            if x[i] = y[j]:
                C[i, j] = C[i-1, j-1] + 1
            else:
                C[i, j] = max(C[i-1, j], C[i, j-1])
    return C[m, n]

시간: $\Theta(mn)$이다. $m \times n$ 테이블을 채우며 각 셀은 $O(1)$에 계산한다.

공간: 테이블에 $\Theta(mn)$이 필요하다(길이만 구할 때는 $O(\min(m,n))$으로 최적화할 수 있다).

2.4 LCS: 단계별 예시

X = ABCBDAB, Y = BDCABA

c B D C A B A
0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
B 0 1 1 2 2 3 3
D 0 1 2 2 2 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4

표 4. X = ABCBDAB, Y = BDCABA의 LCS 테이블 c

LCS 길이 = 4 (예: BCBA). 굵은 칸은 $x_i = y_j$인 곳(대각선 + 1)이다.

그림 7. 역추적 화살표가 있는 LCS 테이블

그림 7. 역추적 화살표가 있는 LCS 테이블

참고: 역추적. 실제 LCS를 복원하려면(길이뿐 아니라) $c[m,n]$에서 역추적한다. $x_i = y_j$이면 해당 문자를 포함하고 대각선으로 이동하며, 그렇지 않으면 더 큰 값 방향으로 이동한다. 그림 7의 음영 칸이 이 규칙으로 따라간 경로이다.

2.5 0-1 배낭 문제

문제: $n$개의 물건이 주어지고, 각 물건의 무게 $w_i$와 가치 $v_i$가 있으며, 용량 $C$인 배낭에 용량을 초과하지 않으면서 총 가치를 최대화하라.

예시: 용량 $C = 10$ kg

물건 무게 가치
1 5 kg 10
2 4 kg 40
3 6 kg 30
4 3 kg 50

표 5. 0-1 배낭 예제의 물건 목록

부분 문제: $K[i, w]$ = 물건 $1 \ldots i$를 고려하고 용량 $w$일 때의 최대 가치.

정답: $K[n, C]$

참고: 0-1 배낭에서 그리디가 실패하는 이유. 가치/무게 비율로 정렬하는 그리디 접근법은 물건을 분할할 수 없기 때문에 작동하지 않는다. 높은 비율의 물건을 선택하면 총 가치가 더 높은 물건 조합을 선택하지 못할 수 있다.

2.6 배낭: 점화식

각 물건 $i$와 용량 $w$에 대해:

$$K[i, w] = \begin{cases} 0 & \text{if } i = 0 \text{ or } w = 0 \\\ K[i-1, w] & \text{if } w_i > w \text{ (물건이 너무 무거움)} \\\ \max(K[i-1, w],\ K[i-1, w - w_i] + v_i) & \text{otherwise} \end{cases}$$

물건 $i$에 대한 두 가지 선택:

  • 가져가지 않으면 가치는 $K[i-1, w]$이다.
  • 가져가면 가치는 $K[i-1, w - w_i] + v_i$이다(공간을 확보하고 가치를 더한다).
Knapsack(n, C):
    for i = 0 to n: K[i, 0] = 0
    for w = 0 to C: K[0, w] = 0
    for i = 1 to n:
        for w = 1 to C:
            if w[i] > w: K[i,w] = K[i-1, w]
            else: K[i,w] = max(K[i-1,w], K[i-1,w-w[i]] + v[i])
    return K[n, C]

2.7 배낭: 풀이 예시

물건(무게, 가치): (5kg, 10), (4kg, 40), (6kg, 30), (3kg, 50). 용량 = 10.

K[i,w] 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
1 (5,10) 0 0 0 0 0 10 10 10 10 10 10
2 (4,40) 0 0 0 0 40 40 40 40 40 50 50
3 (6,30) 0 0 0 0 40 40 40 40 40 50 70
4 (3,50) 0 0 0 50 50 50 50 90 90 90 90

표 6. 0-1 배낭 예제의 DP 테이블 K

최적 가치: $K[4, 10] = 90$ (물건 2와 4: 4kg + 3kg = 7kg, 가치 40 + 50 = 90).

시간: $O(nC)$로 의사다항 시간이다(입력 크기가 아니라 용량 값에 의존한다).

2.8 동전 거스름돈 문제

문제: 동전 단위 $d_1 > d_2 > \cdots > d_k = 1$과 금액 $n$이 주어졌을 때, $n$원을 만들기 위한 최소 동전 수를 구하라.

그리디는 실패할 수 있다. 예시: 동전 = {16, 10, 5, 1}, 금액 = 20.

  • 그리디: 16 + 1 + 1 + 1 + 1 = 5개
  • 최적: 10 + 10 = 2개

DP 점화식:

$$C[j] = \min_{d_i \leq j} \{ C[j - d_i] + 1 \}$$

기저 사례: $C[0] = 0$.

2.9 동전 거스름돈: 알고리즘과 예시

DPCoinChange(n, d[1..k]):
    C[0] = 0
    for j = 1 to n: C[j] = infinity
    for j = 1 to n:
        for i = 1 to k:
            if d[i] <= j and C[j - d[i]] + 1 < C[j]:
                C[j] = C[j - d[i]] + 1
    return C[n]

예시: 동전 = {16, 10, 5, 1}, 금액 = 20

j 0 1 2 3 4 5 6 7 8 9 10 ... 16 ... 20
C[j] 0 1 2 3 4 1 2 3 4 5 1 ... 1 ... 2

표 7. 동전 {16, 10, 5, 1}로 금액 20을 만드는 DP 테이블 C

정답: $C[20] = 2$ (10원짜리 2개). 시간: $O(nk)$.

2.10 플로이드-워셜: 모든 쌍 최단 경로

문제: 가중치 방향 그래프에서 모든 정점 쌍 사이의 최단 경로를 구하라(음수 가중치 사이클은 없다고 가정한다).

핵심 아이디어: 중간 정점 $\{1, 2, \ldots, k\}$를 점진적으로 허용한다.

점화식:

$$ d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right) $$

  • $d_{ij}^{(0)} = w_{ij}$ (직접 간선 가중치, 간선이 없으면 $\infty$)
  • $d_{ii}^{(0)} = 0$

해석: $i$에서 $j$로 갈 때 정점 $k$를 경유하는 것이 더 짧은가, 경유하지 않는 것이 더 짧은가?

2.11 플로이드-워셜: 알고리즘

FloydWarshall(W, n):
    // W[i,j] = 간선 가중치 (간선이 없으면 infinity)
    D = W                    // D^(0) 초기화
    for k = 1 to n:          // 정점 k를 중간으로 추가
        for i = 1 to n:
            for j = 1 to n:
                D[i,j] = min(D[i,j], D[i,k] + D[k,j])
    return D

시간: $O(n^3)$이다. $n$개 정점에 대한 세 겹 중첩 반복이기 때문이다.

공간: $O(n^2)$이다. 거리 행렬 하나를 쓴다.

[자료구조] 입력 $W$는 그래프의 인접 행렬(adjacency matrix) 표현으로, 정점 $n$개인 그래프를 $n \times n$ 배열에 담아 간선 $(i, j)$의 가중치를 $W[i,j]$에서 $O(1)$에 읽게 한다. 플로이드-워셜은 이 행렬을 거리 행렬 $D$로 복사해 매 갱신에서 $D[i,k]$와 $D[k,j]$를 상수 시간에 조회하므로, 세 겹 반복의 각 단계가 $O(1)$이고 전체 시간이 $O(n^3)$이 된다.

참고: 각 반복 $k$는 정점 $\{1, 2, \ldots, k\}$를 중간으로 경유할 수 있는 모든 경로를 고려한다.

2.12 플로이드-워셜: 예시

초기 D^(0):                k=1,2,3,4 후: D^(4):
|   1   2   3   4         |   1   2   3   4
|-------------------      |-------------------
1|  0   3  inf  7         1|  0   3   5   6
2| inf  0   2  inf        2|  5   0   2   3
3|  5  inf  0   1         3|  3   6   0   1
4|  2  inf inf  0         4|  2   5   7   0

그림 8. 플로이드-워셜 예제의 초기 거리 행렬 D(0)과 최종 거리 행렬 D(4)

각 셀 $D[i,j]$에는 이제 $i$에서 $j$까지의 최단 거리가 담겨 있다.

2.13 편집 거리 (레벤슈타인 거리)

문제: 두 문자열 $X[1 \ldots m]$과 $Y[1 \ldots n]$이 주어졌을 때, $X$를 $Y$로 변환하기 위한 단일 문자 연산의 최소 횟수를 구하라.

연산 (각각 비용 1):

  • 문자를 삽입한다.
  • 문자를 삭제한다.
  • 문자를 교체한다.

DP 점화식:

$$E[i,j] = \begin{cases} j & \text{if } i = 0 \\\ i & \text{if } j = 0 \\\ E[i-1,j-1] & \text{if } X[i] = Y[j] \\\ 1 + \min(E[i-1,j],\ E[i,j-1],\ E[i-1,j-1]) & \text{otherwise} \end{cases}$$
  • $E[i-1,j] + 1$은 $X[i]$를 삭제하는 경우이다.
  • $E[i,j-1] + 1$은 $Y[j]$를 삽입하는 경우이다.
  • $E[i-1,j-1] + 1$은 $X[i]$를 $Y[j]$로 교체하는 경우이다.

참고: 응용. 편집 거리는 맞춤법 검사, DNA 서열 정렬, diff 도구, 자연어 처리에서 널리 사용된다.

2.14 편집 거리: 예시

kitten을 sitting으로 변환한다(m=6, n=7).

E $\varepsilon$ s i t t i n g
$\varepsilon$ 0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3

표 8. kitten을 sitting으로 바꾸는 편집 거리 테이블 E

정답: $E[6,7] = 3$이며, 다음 세 번의 연산이 필요하다.

  1. k를 s로 교체한다.
  2. e를 i로 교체한다.
  3. 끝에 g를 삽입한다.

시간: $O(mn)$, 공간: $O(mn)$이며, 거리 값만 구할 때는 공간을 $O(\min(m,n))$으로 줄일 수 있다.



3. DP 문제 풀이 전략

모든 DP 문제에 대한 단계별 접근법:

  1. 부분 문제를 정의한다: $OPT[i, j, \ldots]$가 무엇을 나타내는가?
  2. 점화식을 찾는다: $OPT[\cdot]$가 더 작은 부분 문제와 어떻게 관련되는가?
  3. 기저 사례를 식별한다: 자명한 값이나 경계 값은 무엇인가?
  4. 계산 순서를 결정한다: 테이블을 상향식으로(작은 것에서 큰 것으로) 채운다.
  5. 답을 추출한다: 테이블에서 최종 해는 어디에 있는가?
  6. (선택) 역추적한다: 값뿐 아니라 실제 해를 복원한다.

표 9는 앞에서 다룬 문제의 부분 문제, 점화식, 시간 복잡도를 정리한 것이다.

문제 부분 문제 점화식 시간
피보나치 $f[i]$ $f[i] = f[i-1] + f[i-2]$ $O(n)$
행렬 경로 $c[i,j]$ $c[i,j] = m_{ij} + \max(c[i-1,j], c[i,j-1])$ $O(n^2)$
LCS $c[i,j]$ 일치: $c[i-1,j-1]+1$; 불일치: $\max(c[i-1,j], c[i,j-1])$ $O(mn)$
0-1 배낭 $K[i,w]$ $\max(K[i-1,w], K[i-1,w-w_i]+v_i)$ $O(nC)$
동전 거스름돈 $C[j]$ $\min_{d_i \leq j}(C[j-d_i]+1)$ $O(nk)$
플로이드-워셜 $d_{ij}^{(k)}$ $\min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)}+d_{kj}^{(k-1)})$ $O(n^3)$
편집 거리 $E[i,j]$ 일치: $E[i-1,j-1]$; 불일치: $1+\min(E[i-1,j], E[i,j-1], E[i-1,j-1])$ $O(mn)$

표 9. 대표 DP 문제의 부분 문제, 점화식, 시간 복잡도

참고: 과거를 기억하는 알고리즘. 조지 산타야나는 "과거를 기억하지 못하는 자는 그것을 반복하도록 운명지어진다"라고 썼다. 이미 푼 부분 문제의 해를 기억해 같은 계산을 반복하지 않는 동적 프로그래밍의 발상도 이와 같다.



요약

개념 핵심 요약
동적 프로그래밍 중복 부분 문제의 해를 저장하고 결합하여 최적화 문제를 푼다.
적용 조건 최적 부분 구조와 중복 부분 문제를 모두 갖추어야 한다.
계산 순서 부분 문제에는 암묵적 순서가 있어 작은 부분 문제를 먼저 풀어야 한다.
구현 전략 하향식인 메모이제이션과 상향식인 테이블화의 두 가지 전략이 있다.
DP와 그리디 DP는 모든 부분 문제 조합을 고려하고, 그리디는 하나의 지역적 선택만 한다.
DP와 분할 정복 DP는 부분 문제의 해를 재사용하고, 분할 정복의 부분 문제는 독립적이다.
대표 문제 피보나치는 O(n), 행렬 경로는 $O(n^2)$, LCS와 편집 거리는 O(mn), 0-1 배낭은 O(nC), 동전 거스름돈은 O(nk), 플로이드-워셜은 $O(n^3)$ 시간에 풀린다.


점검 문제

  1. 최적 부분 구조: "최적 부분 구조"가 무엇을 의미하는지 자신의 말로 설명하라. 이 성질이 있는 문제와 없는 문제를 각각 하나씩 예를 들어라.

    정답

    어떤 문제가 최적 부분 구조(optimal substructure) 를 가진다는 것은 그 문제의 최적해가 부분 문제들의 최적해로부터 조립될 수 있음을 의미한다. 최단 경로는 이 성질을 가진다. $s \to t$ 최단 경로의 임의의 부분 경로 역시 그 양 끝점 사이의 최단 경로이므로 플로이드-워셜과 다익스트라가 동작한다. 반면 최장 단순 경로(longest simple path) 는 이 성질을 가지지 않는다. $s \to u$ 최장 단순 경로와 $u \to t$ 최장 단순 경로를 이어 붙이면 정점이 겹칠 수 있으므로, 지역적 최적해의 결합이 전역적 최적해가 되지 않는다(1.2절의 그림 1).

  2. 메모이제이션 vs 테이블화: 하향식(메모이제이션)과 상향식(테이블화) DP의 장단점은 무엇인가? 하나를 다른 것보다 선호할 수 있는 경우는?

    정답

    메모이제이션은 자연스러운 재귀 형태를 유지하며 실제 도달하는 부분 문제만 풀기 때문에 상태 공간이 희소하게 방문될 때(예: 많은 상태가 최초 호출에서 도달할 수 없는 경우) 유리하다. 그러나 재귀 오버헤드와 스택 깊이 한계가 단점이며 깊은 점화식에서는 스택 오버플로가 발생할 수 있다. 테이블화는 의존성 순서로 모든 상태를 순회하여 재귀를 피하고 캐시 지역성과 상수 계수가 더 좋지만, 필요 없는 상태까지 계산할 수 있다. 상태 공간이 크지만 방문이 희소하면 메모이제이션을, 대부분의 상태가 필요하거나 스택 깊이가 문제일 때는 테이블화를 선호한다.

  3. 피보나치: 순진한 재귀로 fib(6)의 호출 트리를 그려라. fib(3)이 몇 번 계산되는가? 그런 다음 메모이제이션이 중복을 어떻게 제거하는지 보여라.

    정답

    fib(6)의 호출 트리는 fib(6) -> fib(5) + fib(4)로 펼쳐지고, 다시 fib(5) -> fib(4) + fib(3) 식으로 기저 사례까지 전개된다. fib(3)은 총 3번 계산된다. 두 개의 fib(4) 아래에서 각각 한 번, 그리고 fib(5) 아래에서 한 번이다. 메모이제이션은 f[n]을 처음 계산할 때 저장하므로 이후 호출은 $O(1)$에 즉시 반환한다. 서로 다른 부분 문제는 단지 $n$개뿐이므로 $O(2^n)$의 지수적 계산이 $O(n)$의 선형 계산으로 축소된다.

  4. LCS: X = ABCB와 Y = BDCB에 대해 LCS 테이블을 계산하라. LCS 길이는? 역추적하여 실제 LCS를 구하라.

    정답

    일치 시 $c[i,j] = c[i-1,j-1]+1$, 불일치 시 $\max(c[i-1,j], c[i,j-1])$로 테이블을 채우면 최종적으로 $c[4,4] = 3$. LCS 길이 = 3. $c[4,4]$에서부터 역추적: $X_4=B=Y_4$ → B 채택, 대각선 이동; $X_3=C=Y_3$ → C 채택, 대각선 이동; 수평 이동 후 $X_2=B=Y_1$ → B 채택. 역순으로 모으면 LCS = BCB.

  5. 0-1 배낭: 물건 (무게, 가치): (2, 12), (1, 10), (3, 20), (2, 15)와 용량 5가 주어졌을 때 DP 테이블을 채워라. 최적 가치는 얼마이며 어떤 물건이 선택되는가?

    정답

    점화식 $K[i,w] = \max(K[i-1,w],\ K[i-1, w-w_i]+v_i)$를 행별로 적용하면 $K[1,5]=12$, $K[2,5]=22$, $K[3,5]=32$, $K[4,5]=37$. 역추적: $K[4,5] \neq K[3,5]$ → 물건 4 담기 (w=2, v=15), 용량 3; $K[3,3]=K[2,3]=22$ → 물건 3 건너뛰기; $K[2,3] \neq K[1,3]$ → 물건 2 담기 (w=1, v=10), 용량 2; $K[1,2] \neq K[0,2]$ → 물건 1 담기 (w=2, v=12). 선택된 물건: {1, 2, 4}, 총 무게 $2+1+2=5$, 총 가치 $12+10+15=$ 37.

  6. 동전 거스름돈: 단위 {25, 10, 6, 1}로 금액 30에 대한 최소 동전 수를 DP로 구하라. 그리디 접근법(가장 큰 동전 우선)이 왜 차선의 답을 주는지 보여라.

    정답

    그리디는 25를 먼저 고르고 남은 5를 1+1+1+1+1로 채워 총 6개가 된다. DP는 $C[j] = \min_{d_i \leq j}(C[j-d_i]+1)$로 각 금액에서 모든 단위를 시도하므로 $C[30] = C[20]+1$이 되고, $C[20]=2$ (10원짜리 두 개)이므로 $C[30]=$ 3개 (10+10+10). 그리디가 실패하는 이유는 25를 선택한 직후 남은 금액을 효율적으로 채울 수 없기 때문이다. DP는 매 금액에서 모든 동전 선택지를 고려하므로 25를 아예 사용하지 않는 더 나은 조합을 발견한다.

  7. 플로이드-워셜: 2.12절의 4개 정점 그래프에서 알고리즘의 한 반복(k=2)을 추적하라. 어떤 셀이 바뀌며 왜 그런가?

    정답

    $k=2$ 반복은 모든 쌍 $(i,j)$에 대해 $D[i,j] \gets \min(D[i,j],\ D[i,2] + D[2,j])$를 수행한다. 2.12절의 예에서 $k=1$ 반복 뒤의 $D^{(1)}$은 $D^{(0)}$에서 $D[3,2] = 8$, $D[4,2] = 5$만 바뀐 행렬이다. $k=2$에서 $D^{(1)}[3,4] = 1$은 그대로이고, $D^{(1)}[1,3] = \infty$는 $\min(\infty, D[1,2]+D[2,3]) = \min(\infty, 3+2) = 5$로, $D^{(1)}[4,3] = \infty$는 $\min(\infty, D[4,2]+D[2,3]) = \min(\infty, 5+2) = 7$로 갱신된다. $D[1,4]=7$은 $D[2,4]=\infty$여서 변하지 않는다. 갱신되는 셀은 정확히 정점 2를 경유하는 경로가 기존 최단 거리보다 짧은 경우이며, 기존 경로가 더 짧거나 같은 셀은 그대로 유지된다.

  8. 편집 거리: sunday와 saturday 사이의 편집 거리를 계산하라. DP 테이블을 보이고 필요한 연산들을 식별하라.

    정답

    $X=$ sunday (m=6), $Y=$ saturday (n=8)에 대해 점화식을 적용하면 $E[6,8]=3$ 이다. 정렬해 보면 첫 글자 s는 일치하고, 그 다음 u 앞에 a와 t를 삽입해야 하며(삽입 2회), 그 후 u-n-d-a-y를 u-r-d-a-y에 맞추기 위해 n을 r로 한 번 교체한다. 따라서 세 연산은 a 삽입, t 삽입, n을 r로 교체이며, 이는 최소인 3회의 단일 문자 편집이다.