동적 프로그래밍(Dynamic Programming)이란 무엇이며 메모이제이션과 타뷸레이션의 차이는?

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 부분 문제(Subproblem)로 나누어 풀고, 이미 계산한 결과를 저장하여 재사용함으로써 중복 계산을 제거하는 최적화 기법입니다. 단순 분할 정복(Divide & Conquer)과 달리, DP는 부분 문제들이 서로 겹치는 경우에 효과적입니다. 구현 방식에 따라 하향식(Top-down) 메모이제이션과 상향식(Bottom-up) 타뷸레이션으로 나뉩니다.

DP 적용 조건

동적 프로그래밍을 적용하려면 두 가지 조건을 만족해야 합니다.

1. 최적 부분 구조 (Optimal Substructure)

문제의 최적해가 부분 문제들의 최적해로 구성될 수 있어야 합니다.

최단 경로 문제:
A → B → C → D의 최단 경로는
A → B의 최단 경로 + B → C의 최단 경로 + C → D의 최단 경로

fib(n) = fib(n-1) + fib(n-2)
→ fib(n)의 해가 더 작은 부분 문제의 해로 구성됨

2. 중복 부분 문제 (Overlapping Subproblems)

같은 부분 문제가 여러 번 반복해서 계산됩니다.

fib(5) 계산 시:
fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)  ← 중복
│   │   └── fib(1)
│   └── fib(2)      ← 중복
└── fib(3)          ← 중복
    ├── fib(2)      ← 중복
    └── fib(1)

fib(2)가 3번, fib(3)이 2번 계산됨 → 비효율적!

메모이제이션 (Memoization) - Top-down

개념

재귀 + 캐시 방식입니다. 함수를 재귀적으로 호출하되, 이미 계산한 결과는 캐시(메모)에 저장하여 동일한 계산을 반복하지 않습니다.

Top-down: 큰 문제 → 작은 문제 순서로 풀어 내려감

피보나치 구현 비교

# 순수 재귀 - O(2ⁿ)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# 메모이제이션 적용 - O(n)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]  # 이미 계산된 값 반환
    if n <= 1:
        return n

    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Python functools.lru_cache 활용
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n-1) + fib_cached(n-2)

print(fib_cached(100))  # 354224848179261915075 (즉시 계산!)

메모이제이션의 동작 과정

fib_memo(5) 호출 시:

호출 1: fib(5) → memo에 없음 → fib(4) + fib(3) 계산 필요
호출 2: fib(4) → memo에 없음 → fib(3) + fib(2) 계산 필요
호출 3: fib(3) → memo에 없음 → fib(2) + fib(1) 계산 필요
호출 4: fib(2) → memo에 없음 → fib(1) + fib(0) = 1 → memo[2] = 1
호출 5: fib(1) → 반환 1
호출 3 완료: fib(3) = 1 + 1 = 2 → memo[3] = 2
호출 6: fib(2) → memo에 있음! → 바로 1 반환 ★
호출 2 완료: fib(4) = 2 + 1 = 3 → memo[4] = 3
호출 7: fib(3) → memo에 있음! → 바로 2 반환 ★
호출 1 완료: fib(5) = 3 + 2 = 5 → memo[5] = 5

타뷸레이션 (Tabulation) - Bottom-up

개념

반복문 + 테이블 방식입니다. 가장 작은 부분 문제부터 차례로 풀어 올라가며 결과를 테이블(배열)에 저장합니다.

Bottom-up: 작은 문제 → 큰 문제 순서로 쌓아 올라감

피보나치 타뷸레이션

def fib_tabulation(n):
    if n <= 1:
        return n

    # 테이블 초기화
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    # 작은 문제부터 순서대로 계산
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

# dp 테이블 (n=7):
# dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5, dp[6]=8, dp[7]=13

# 공간 최적화: O(n) → O(1)
def fib_optimized(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

대표적인 DP 문제

1. 배낭 문제 (0/1 Knapsack)

def knapsack(weights, values, capacity):
    """
    weights: 각 물건의 무게
    values:  각 물건의 가치
    capacity: 배낭의 최대 무게
    """
    n = len(weights)
    # dp[i][w] = i번째 물건까지 고려했을 때 무게 w 이하로 담을 수 있는 최대 가치
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 현재 물건을 담지 않는 경우
            dp[i][w] = dp[i-1][w]

            # 현재 물건을 담는 경우 (무게가 허용될 때)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity))  # 10

2. 최장 공통 부분 수열 (LCS)

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[:i]와 s2[:j]의 LCS 길이
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1  # 문자 일치
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 최대 선택

    return dp[m][n]

print(lcs("ABCBDAB", "BDCAB"))  # 4 (BCAB 또는 BDAB)

3. 동전 거스름돈 (Coin Change)

def coin_change(coins, amount):
    """최소 동전 개수로 amount 만들기"""
    # dp[i] = 금액 i를 만들기 위한 최소 동전 수
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 금액 0은 동전 0개

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

coins = [1, 5, 10, 25]
print(coin_change(coins, 41))  # 4 (25+10+5+1)

4. 최장 증가 부분 수열 (LIS)

def lis(arr):
    """Longest Increasing Subsequence"""
    n = len(arr)
    # dp[i] = arr[i]로 끝나는 LIS의 길이
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 (2,3,7,101 또는 2,5,7,101)

메모이제이션 vs 타뷸레이션 상세 비교

# 격자 경로 수 세기 - 두 방식 비교
# m×n 격자에서 왼쪽 위 → 오른쪽 아래로 가는 경우의 수 (오른쪽/아래로만 이동)

# 메모이제이션 방식 (Top-down)
def unique_paths_memo(m, n, memo={}):
    if (m, n) in memo:
        return memo[(m, n)]
    if m == 1 or n == 1:
        return 1

    result = unique_paths_memo(m-1, n, memo) + unique_paths_memo(m, n-1, memo)
    memo[(m, n)] = result
    return result

# 타뷸레이션 방식 (Bottom-up)
def unique_paths_tab(m, n):
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

print(unique_paths_memo(3, 7))  # 28
print(unique_paths_tab(3, 7))   # 28

DP 접근법 선택 가이드

DP 적용 여부 판단:
1. 재귀로 풀 수 있나? YES
2. 중복 부분 문제가 있나? YES
3. 최적 부분 구조가 있나? YES
→ DP 적용!

메모이제이션 선택:
- 모든 상태를 계산할 필요가 없을 때 (필요한 것만 계산)
- 재귀가 더 직관적인 경우
- 스택 오버플로우 위험이 없는 경우

타뷸레이션 선택:
- 모든 상태를 계산해야 할 때
- 공간 최적화가 필요한 경우 (이전 행만 유지 가능)
- 재귀 호출 오버헤드를 줄이고 싶을 때
- 스택 오버플로우 우려가 있을 때 (n이 매우 클 때)

메모이제이션 vs 타뷸레이션 비교표

특성	메모이제이션 (Top-down)	타뷸레이션 (Bottom-up)
방향	큰 문제 → 작은 문제	작은 문제 → 큰 문제
구현 방식	재귀 + 캐시	반복문 + 배열
코드 직관성	높음 (점화식과 유사)	중간
실행 속도	약간 느림 (재귀 오버헤드)	빠름
공간 효율	필요한 것만 계산	모든 상태 계산
스택 오버플로우	가능 (재귀 깊이 제한)	없음
공간 최적화	어려움	쉬움 (슬라이딩 윈도우)
적합한 경우	일부 상태만 필요할 때	모든 상태 계산 시