[자료구조와 알고리즘 with 파이썬] 11 동적 계획법

11-1 동적 계획법이란?
11-2 최장 공통 부분 순서
11-3 배낭 채우기

---

11-1 동적계획법이란?

동적 계획법이란?

• 큰 문제를 작은 문제로 나누고, 중복되는 작은 문제의 해답을 저장하여 반복 계산을 피하는 알고리즘 설계 기법
• 핵심은 같은 문제를 두 번 이상 풀지 않는다

분할 정복과의 차이

항목	분할 정복	동적 계획법
문제 분할	O	O
부분 문제의 중복	✕	O (중복 발생)
해답 저장	✕	O (메모리에 저장)
대표 예시	병합 정렬, 이진 탐색	피보나치 수열, 최장 공통 부분 수열

피보나치 수열로 이해하는 동적 계획법

• 피보나치 수열의 정의

fib(0) = 0  
fib(1) = 1  
fib(n) = fib(n-1) + fib(n-2) (n ≥ 2)

분할 정복 방식 : 비효율적

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

• 시간 복잡도: O(2ⁿ)
• 같은 값을 계속 다시 계산 → 비효율

메모이제이션 방식 (Top-down)

mem = [None] * (n + 1)

def fib_dp_mem(n):
    if mem[n] is not None:
        return mem[n]
    if n < 2:
        mem[n] = n
    else:
        mem[n] = fib_dp_mem(n-1) + fib_dp_mem(n-2)
    return mem[n]

• 핵심 특징: 재귀 + 저장
• 시간 복잡도: O(n)
• 공간 복잡도: O(n)
• 같은 문제는 딱 한 번만 풂
• 전역 리스트 mem을 이용해 저장

테이블화 방식 (Bottom-up)

def fib_dp_tab(n):
    f = [None] * (n + 1)
    f[0], f[1] = 0, 1
    for i in range(2, n + 1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

• 순차적으로 작은 문제부터 해결
• 반복문 기반으로 구현
• 시간 복잡도: O(n)
• 공간 복잡도: O(n)
• 전역 변수 없이 구현 가능 → 코드가 깔끔함

동적 계획법의 핵심 조건

1. 중복 부분 문제 (Overlapping Subproblems)
   • 이미 계산한 결과를 다시 계산할 필요가 있을 때
2. 최적 부분 구조 (Optimal Substructure)
   • 작은 문제의 해답을 이용해서 큰 문제의 해답을 만들 수 있을 때
3. 분할 정복이 가능한 구조

예외

• 이진 탐색, 병합 정렬 등은 부분 문제의 중복이 없기 때문에 동적 계획법에 적합하지 않음

동적 계획법은 언제 쓰는가?

-> 중복되는 계산이 많고, 한번 구한 값을 다시 활용할 수 있으며, 최적의 해를 작은 문제에서 유도할 수 있는 문제

11-2 최장 공통 부분 순서

최장 공통 부분 순서(LCS)란 무엇인가?

• 두 문자열에서 순서를 유지한 채로 공통으로 존재하는 가장 긴 부분 문자열의 길이를 찾는 문제

• 예시

  • X: HELLO WORLD
  • Y: GAME OVER
  • LCS: E OR (길이 3)

• 유전자 분석, 파일 차이 비교, 문자열 유사도 판단 등 다양한 분야에서 사용됨

문제 접근 방식

• 단순한 비교만으로는 해결이 어려움
• 부분 문제로 나누고 그 결과를 조합하는 구조가 필요함
• 동적 계획법(DP)이 매우 효과적임

분할 정복 방식 (재귀 호출)

def lcs_recur(X, Y, m, n):
    if m == 0 or n == 0:
        return 0
    if X[m-1] == Y[n-1]:
        return 1 + lcs_recur(X, Y, m-1, n-1)
    else:
        return max(lcs_recur(X, Y, m, n-1), lcs_recur(X, Y, m-1, n))

• 단점: 같은 부분 문제를 반복해서 풀어야 함 → 비효율적
• 시간복잡도: O(2^n)

동적 계획법 (테이블화, Bottom-Up 방식)

• 순환 관계 정리

L[i][j] = 
  0                          if i == 0 or j == 0
  L[i-1][j-1] + 1            if X[i-1] == Y[j-1]
  max(L[i-1][j], L[i][j-1])  otherwise

• 예시

def lcs_dp(X, Y):
    m, n = len(X), len(Y)
    L = [[0] * (n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
                
    return L[m][n]

• 시간복잡도: O(mn)
• 공간복잡도: O(mn)
• 장점: 모든 부분 문제는 한 번만 계산됨 → 효율적

LCS 테이블 추적 (문자열 구하기)

• 테이블을 오른쪽 아래에서 시작해 위 또는 왼쪽으로 이동하며 추적하면 됨

• 추적 알고리즘

def lcs_dp_traceback(X, Y, L):
    i, j = len(X), len(Y)
    lcs = ""
    
    while i > 0 and j > 0:
        v = L[i][j]
        if v > L[i-1][j] and v > L[i][j-1] and v > L[i-1][j-1]:
            i -= 1
            j -= 1
            lcs = X[i] + lcs
        elif v == L[i][j-1] and v > L[i-1][j]:
            j -= 1
        else:
            i -= 1
            
    return lcs

• 예시

X = "GAME OVER"
Y = "HELLO WORLD"
L = [[0] * (len(Y)+1) for _ in range(len(X)+1)]
lcs_dp(X, Y)  # 테이블 생성
lcs_dp_traceback(X, Y, L)  # LCS = "EOR"

11-3 배낭 채우기

문제 정의

• 무게(weight)와 가치(value)가 주어진 n개의 물건 중에서 총 무게가 W를 넘지 않도록 물건을 골라 배낭에 넣을 때, 가치의 합이 최대가 되도록 선택하는 문제
• 단, 물건은 쪼개서 넣을 수 없으며, 각 물건은 한 번만 넣을 수 있음

문제 예시

val = [60, 100, 190, 120, 200, 150]
wt  = [ 2,   5,   8,   4,   7,   6]
W = 18  # 배낭의 최대 용량

기존 접근의 한계

• 완전탐색 (모든 조합 확인)

  • 각 물건을 넣거나 안 넣거나 → 경우의 수: 2^n
  • 비효율적 (지수 시간 소요)

• 탐욕적 접근 (가치/무게 비율 기준 선택)

  • 물건을 나눠 넣을 수 없기 때문에 정확한 해를 보장하지 않음

동적 계획법으로 접근하기

• 핵심 아이디어
  • 전체 문제를 작은 부분 문제들로 나눠서 푸는 방식
  • 즉, 이전에 푼 문제의 해를 활용해 더 큰 문제를 해결

문제 해결

점화식 정의 (재귀 관계)

• A(n, W) = n개의 물건을 고려할 때, 용량 W인 배낭에 넣을 수 있는 최대 가치

  A(n, W) =
  0                                  if n == 0 or W == 0
  A(n-1, W)                          if wt[n-1] > W
  max(
      A(n-1, W),                     # 현재 물건을 넣지 않는 경우
      val[n-1] + A(n-1, W - wt[n-1]) # 현재 물건을 넣는 경우
  )                                 otherwise

• 재귀(분할 정복) 구현 예시

def knapsack_dc(W, wt, val, n):
    if n == 0 or W == 0:
        return 0
    if wt[n-1] > W:
        return knapsack_dc(W, wt, val, n-1)
    else:
        val_with = val[n-1] + knapsack_dc(W - wt[n-1], wt, val, n-1)
        val_without = knapsack_dc(W, wt, val, n-1)
        return max(val_with, val_without)

• 비효율적: 중복된 부분 문제들을 계속 반복해서 계산함 → 지수 시간

동적 계획법(DP) 구현 예시

• 2차원 테이블 활용

  def knapsack_dp(W, wt, val, n):
    A = [[0] * (W + 1) for _ in range(n + 1)]  # 테이블 초기화
    
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i-1] > w:
                A[i][w] = A[i-1][w]
            else:
                val_with = val[i-1] + A[i-1][w - wt[i-1]]
                val_without = A[i-1][w]
                A[i][w] = max(val_with, val_without)
                
    return A[n][W]

  val = [60, 100, 190, 120, 200, 150]
  wt  = [2, 5, 8, 4, 7, 6]
  W = 18
  n = len(val)
  
  print("0-1 배낭 문제 (분할 정복):", knapsack_dc(W, wt, val, n))
  print("0-1 배낭 문제 (동적 계획법):", knapsack_dp(W, wt, val, n))

• 실행 결과

  0-1 배낭 문제 (분할 정복): 480
  0-1 배낭 문제 (동적 계획법): 480

• 주의 사항
  • 물건의 무게는 반드시 정수여야 함
    (실수 무게로는 테이블 인덱스를 만들 수 없음)
  • W가 너무 크거나, 물건 종류가 많으면 공간이 부족해질 수 있음

결과 비교

방법	시간 복잡도	공간 복잡도	특징
분할 정복	O(2^n)	O(1)	중복 호출 많음
동적 계획법	O(nW)	O(nW)	효율적, 실전 사용 가능

• n: 물건 개수
• W: 배낭 용량