CS학습2026년 8월 24일

Dynamic Programming: 부분 문제의 중복 계산을 메모이제이션으로 제거하는 기법

Dynamic Programming(동적 계획법)은 큰 문제를 작은 부분 문제로 나누고, 이미 계산한 부분 문제의 결과를 저장해 재사용함으로써 지수 시간 복잡도를 다항 시간으로 줄이는 알고리즘 설계 기법이다. 재귀적 분할 정복(Divide and Conquer)과 달리 부분 문제가 서로 겹친다는 점이 핵심이며, 이 겹침을 활용하지 않으면 동일한 계산을 반복

송민성6분 읽기

1. 개념

Dynamic Programming(DP)은 큰 문제를 작은 부분 문제(Subproblem)로 쪼개서 풀고, 그 결과를 저장했다가 나중에 재사용하는 알고리즘 설계 기법이다.

DP가 적용 가능하려면 문제가 다음 두 가지 성질을 만족해야 한다.

최적 부분 구조(Optimal Substructure): 문제의 최적해가 부분 문제의 최적해로 구성될 수 있다.
중복 부분 문제(Overlapping Subproblems): 동일한 부분 문제가 재귀 호출 과정에서 여러 번 반복해서 등장한다.

두 번째 성질이 분할 정복(Divide and Conquer)과의 차이점이다. 병합 정렬(Merge Sort)처럼 분할 정복은 부분 문제가 서로 겹치지 않기 때문에 DP를 적용할 이유가 없다.

2. 왜 사용하는가

피보나치 수열을 순수 재귀로 계산하면 fib(n) = fib(n-1) + fib(n-2) 호출이 반복되면서 동일한 fib(k) 값을 지수적으로 여러 번 계산한다. fib(5)를 계산하는 재귀 트리를 그려보면 fib(2)가 3번, fib(1)이 5번 호출된다. n이 커질수록 호출 횟수는 대략 O(2^n)에 가깝게 폭증한다.

DP는 한 번 계산한 fib(k)의 결과를 배열이나 해시맵에 저장해두고, 다음에 같은 값이 필요할 때 재계산 대신 저장된 값을 꺼내 쓴다. 이 저장-재사용 구조 덕분에 O(2^n)이던 시간 복잡도가 O(n)으로 줄어든다. 결국 DP는 "시간을 공간과 교환하는" 트레이드오프다.

3. 동작 원리

DP를 구현하는 두 가지 접근 방식이 있다.

메모이제이션(Memoization, Top-down) 재귀 함수를 그대로 사용하되, 함수 호출 결과를 캐시(보통 배열이나 딕셔너리)에 저장한다. 호출 시 캐시에 값이 있으면 즉시 반환하고, 없으면 계산 후 캐시에 저장한다.

타뷸레이션(Tabulation, Bottom-up) 재귀를 쓰지 않고 가장 작은 부분 문제부터 반복문으로 순서대로 채워나간다. 배열(테이블)을 인덱스 순서대로 채우면서 최종 답까지 도달한다.

두 방식은 계산하는 부분 문제의 집합이 다를 수 있다. Top-down은 실제로 필요한 부분 문제만 계산하지만 재귀 호출 오버헤드가 있고, Bottom-up은 모든 부분 문제를 순서대로 계산하지만 재귀 스택이 없어 오버헤드가 적다.

4. 코드 예제

피보나치: 세 가지 구현 비교

python

import time
from functools import lru_cache

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

# 2) 메모이제이션 (Top-down) - O(n)
def fib_memo(n: int, cache: dict = None) -> int:
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

# 2-1) 파이썬 내장 데코레이터로 동일하게 구현
@lru_cache(maxsize=None)
def fib_lru(n: int) -> int:
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

# 3) 타뷸레이션 (Bottom-up) - O(n), 공간 O(1)로 최적화 가능
def fib_tabulation(n: int) -> int:
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1


if __name__ == "__main__":
    n = 30
    start = time.perf_counter()
    print(fib_naive(n))
    print(f"naive: {time.perf_counter() - start:.4f}s")

    start = time.perf_counter()
    print(fib_memo(n))
    print(f"memo: {time.perf_counter() - start:.6f}s")

    start = time.perf_counter()
    print(fib_tabulation(n))
    print(f"tabulation: {time.perf_counter() - start:.6f}s")

대표 응용: 배낭 문제(0/1 Knapsack)

물건마다 무게와 가치가 있고, 배낭의 무게 제한 안에서 최대 가치를 구하는 문제다. dp[i][w]를 "i번째 물건까지 고려했을 때 무게 w 이하로 담을 수 있는 최대 가치"로 정의한다.

python

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    # dp[i][w]: i개의 물건 중 선택, 무게 한도 w일 때 최대 가치
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w_i, v_i = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            # 물건 i를 담지 않는 경우
            dp[i][w] = dp[i - 1][w]
            # 물건 i를 담을 수 있고, 담는 것이 더 이득인 경우
            if w >= w_i:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - w_i] + v_i)

    return dp[n][capacity]


weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # 7 (무게 2+3=5, 가치 3+4=7)

5. 시간 복잡도 또는 성능 특성

| 구현 방식 | 시간 복잡도 | 공간 복잡도 | 비고 | |---|---|---|---| | 피보나치 순수 재귀 | O(2^n) | O(n) (재귀 스택) | 실용성 없음 | | 피보나치 메모이제이션 | O(n) | O(n) | 재귀 호출 오버헤드 존재 | | 피보나치 타뷸레이션 | O(n) | O(n) → O(1) 최적화 가능 | 반복문만 사용 | | 0/1 배낭 문제 | O(n × capacity) | O(n × capacity) → O(capacity)로 최적화 가능 | n=물건 개수 |

배낭 문제처럼 dp[i][w]가 바로 이전 행(dp[i-1][*])만 참조하는 경우, 2차원 배열 대신 1차원 배열을 뒤에서부터 순회하며 갱신하면 공간 복잡도를 O(capacity)로 줄일 수 있다. 이를 "롤링 배열(Rolling Array)" 최적화라고 부른다.

6. 실무 사용 사례

문자열 편집 거리(Edit Distance): diff 도구나 맞춤법 검사기에서 두 문자열 간 최소 편집 연산 횟수를 계산할 때 사용한다(Levenshtein Distance).
최장 공통 부분 수열(LCS): git diff, 버전 관리 시스템의 파일 비교 알고리즘의 기반이다.
DB 쿼리 최적화: 일부 RDBMS의 쿼리 플래너가 조인 순서를 결정할 때 동적 계획법 기반 비용 모델을 사용한다.
자연어 처리: 은닉 마르코프 모델(HMM)의 비터비 알고리즘(Viterbi Algorithm)은 DP로 최적 경로를 찾는다.
네트워크 라우팅: 벨만-포드(Bellman-Ford) 최단 경로 알고리즘은 DP의 한 형태다.

7. 주의할 점

점화식을 먼저 세워라: 코드를 짜기 전에 "부분 문제를 어떻게 정의하고, 어떤 점화식으로 이어지는지"를 종이에 먼저 정리해야 한다. 점화식 없이 코드부터 짜면 잘못된 상태 정의로 시간을 낭비한다.
재귀 깊이 제한: Python은 기본 재귀 깊이 제한이 1000이다. 메모이제이션을 재귀로 구현할 때 n이 크면 RecursionError가 발생할 수 있으므로, 이런 경우 타뷸레이션으로 전환하거나 sys.setrecursionlimit()을 조정해야 한다.
상태 공간이 너무 크면 DP가 답이 아닐 수 있다: dp 테이블 크기가 메모리를 초과하면(예: 상태가 3차원 이상이고 각 차원이 10^5 이상) DP 자체를 재검토하거나 상태 압축이 필요하다.
탐욕 알고리즘(Greedy Algorithm)과 혼동하지 말 것: 최적 부분 구조가 있다고 해서 항상 그리디가 통하는 것은 아니다. 그리디는 각 단계에서 부분 문제 간 독립적인 지역 최적 선택이 전역 최적으로 이어질 때만 성립하며, 배낭 문제(0/1)처럼 그리디로 풀리지 않는 경우가 많다.

8. 핵심 정리

DP는 최적 부분 구조와 중복 부분 문제라는 두 조건을 만족하는 문제에서, 부분 문제의 계산 결과를 저장해 재사용함으로써 지수 시간을 다항 시간으로 줄이는 기법이다. Top-down 메모이제이션은 재귀 구조를 유지하며 필요한 부분만 계산하고, Bottom-up 타뷸레이션은 반복문으로 전체 테이블을 채운다. 실무에서는 문자열 비교, 경로 탐색, 리소스 최적화 문제에서 폭넓게 쓰이며, 점화식 설계와 상태 공간 크기 파악이 구현의 핵심이다.