동적 계획법 (Dynamic Programming)

동적 계획법은 복잡한 문제를 간단한 여러 개의 작은 문제로 나누어 풀고, 한 번 구한 답은 저장해 두었다가 다시 쓰는 방법입니다. 흔히 말하는 DP가 바로 동적 계획법입니다.

한눈에 보기

한 가지 문제에 대해서, 단 한 번만 풀도록 만들어 주는 알고리즘입니다. 즉, 똑같은 연산을 반복하지 않도록 만들어 줍니다. 실행 시간을 줄이기 위해 많이 쓰는 수학적 접근 방식의 알고리즘이라고 할 수 있습니다.

비유하면 이렇습니다. 수학 문제집을 풀다가 이미 푼 문제가 또 나오면, 처음부터 다시 풀지 않고 노트에 적어 둔 답을 그대로 옮겨 적습니다. 이 "답 노트"가 DP의 핵심입니다.

동적 계획법이 효과를 발휘하려면 문제가 다음 두 성질을 가져야 합니다.

성질	뜻	피보나치 예
겹치는 부분 문제 (Overlapping Subproblems)	답을 구하는 동안 이미 했던 똑같은 계산이 계속 반복됨	fib(5)를 구하다 보면 fib(3)을 여러 번 구함
최적 부분 구조 (Optimal Substructure)	큰 문제의 답을 작은 문제들의 답으로 만들 수 있음	fib(n) = fib(n-1) + fib(n-2)

"반복되는 계산"은 겹치는 부분 문제 쪽 설명이고, 최적 부분 구조는 "작은 문제의 답을 조합하면 큰 문제의 답이 된다"는 뜻입니다. 두 성질이 모두 있어야 DP를 쓸 수 있습니다.

접근 방식

커다란 문제를 작게 쪼개서 해결한다는 점에서 병합 정렬 같은 분할 정복과 매우 비슷합니다. 하지만 작은 문제로 만드는 과정에서 중복 여부가 다릅니다.

구분	분할 정복	동적 계획법
작은 문제끼리 겹치나?	겹치지 않음 (왼쪽 절반, 오른쪽 절반처럼 따로따로)	겹침 (같은 작은 문제가 여러 번 등장)
저장이 필요한가?	필요 없음	구한 답을 저장해 재사용

즉, 동적 계획법은 작은 문제들 속에서 계속 반복되는 연산을 저장해 두고 활용해서 빠르게 푸는 것이 핵심입니다.

조건

• 작은 문제에서 반복이 일어남
• 같은 문제는 항상 정답이 같음

이 두 가지 조건이 충족된다면 동적 계획법으로 문제를 풀 수 있습니다. 같은 문제가 항상 정답이 같고, 반복적으로 일어난다는 점을 활용해 메모이제이션(Memoization) 으로 큰 문제를 해결해 나가는 것입니다.

• 메모이제이션(Memoization): 한 번 계산한 문제는 다시 계산하지 않도록 저장해 두고 활용하는 방식

동작 과정

피보나치 수열(1, 1, 2, 3, 5, 8, ... 앞의 두 수를 더해 다음 수를 만드는 수열)로 살펴보겠습니다. 재귀로 그냥 풀면 같은 연산을 계속 반복합니다.

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)

이처럼 같은 연산이 계속 반복적으로 이용될 때, 메모이제이션을 활용하여 값을 미리 저장해두면 효율적

fib(5)를 그냥 재귀로 구할 때 각 값이 몇 번 계산되는지 세어 보면 다음과 같습니다.

계산	호출 횟수
fib(5)	1번
fib(4)	1번
fib(3)	2번
fib(2)	3번
fib(1)	2번
합계	9번

n이 커질수록 중복이 폭발적으로 늘어납니다. fib(20)만 해도 함수가 13,529번 호출됩니다. 이때 메모이제이션으로 같은 작업을 되풀이하지 않도록 구현하면 효율적입니다.

DP로 풀 때의 순서는 다음과 같습니다.

1. 가장 작은 문제의 답을 정합니다. (fib(1) = 1, fib(2) = 1)
2. 작은 문제를 풀어 보며 규칙을 찾아 점화식을 세웁니다. (fib(i) = fib(i-1) + fib(i-2))
3. 작은 문제부터 표에 답을 채워 나갑니다. 필요한 값은 이미 표에 있습니다.

i	계산	dp[i]
1	시작 값	1
2	시작 값	1
3	dp[2] + dp[1] = 1 + 1	2
4	dp[3] + dp[2] = 2 + 1	3
5	dp[4] + dp[3] = 3 + 2	5

표를 한 칸씩 채우기만 하면 되므로, 각 값은 딱 한 번만 계산됩니다.

아래 그림은 F5를 구할 때 어떤 값이 어떤 값을 필요로 하는지 그린 것입니다. 그냥 재귀로 풀면 F3, F2를 여러 번 계산하지만, 답을 저장해 두면 부분 문제는 F1 ~ F5 다섯 개뿐이고 각각 한 번씩만 풀면 됩니다.

그림 출처: Wikimedia Commons (퍼블릭 도메인)

구현 방식

• Bottom-up: 작은 문제부터 차근차근 구하는 방법 (반복문으로 표 채우기, 타뷸레이션이라고도 함)
• Top-down: 큰 문제를 풀다가 풀리지 않은 작은 문제가 있으면 그때 해결하는 방법 (재귀 + 메모이제이션)

방식	좋은 점	주의할 점
Bottom-up	재귀가 없어 함수 호출 비용이 없고, 재귀 깊이 제한에 걸리지 않음	어떤 순서로 표를 채울지 직접 정해야 해서, 점화식이 코드에 덜 드러나 가독성이 떨어질 수 있음
Top-down	점화식을 거의 그대로 재귀로 옮기므로 읽기 쉬움	재귀 호출이 깊어지면 Python 기본 재귀 한도(약 1000)에 걸릴 수 있음

원문은 "Bottom-up은 해결이 용이하지만 가독성이 떨어지고, Top-down은 가독성이 좋지만 코드 작성이 힘들다"고 정리합니다. 가독성 비교는 위 표와 같고, Top-down의 실제 어려움은 코드 길이보다 재귀 깊이와 호출 비용 쪽에 있다고 보면 됩니다.

동적 계획법으로 문제를 풀 때는 우선 작은 문제부터 해결해 보는 것이 좋습니다. 작은 문제들을 풀다 보면 이전에 구해 둔 더 작은 문제들이 활용되는 것을 확인하게 됩니다. 이 규칙을 찾았을 때 점화식을 도출해 동적 계획법을 적용합니다.

Python 코드

# 1. 그냥 재귀: 같은 계산을 계속 반복
calls = 0

def fib_naive(n):
    global calls
    calls += 1
    if n <= 2:
        return 1
    return fib_naive(n - 1) + fib_naive(n - 2)


# 2. Top-down: 재귀 + 메모이제이션
def fib_top_down(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 2:
        return 1
    if n in memo:                      # 이미 푼 문제면 저장된 답을 바로 사용
        return memo[n]
    memo[n] = fib_top_down(n - 1, memo) + fib_top_down(n - 2, memo)
    return memo[n]


# 3. Bottom-up: 작은 문제부터 표를 채우기
def fib_bottom_up(n):
    if n <= 2:
        return 1
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 점화식
    return dp[n]


# 4. Bottom-up + 공간 절약: 직전 두 값만 기억
def fib_two_vars(n):
    a, b = 1, 1                        # fib(1), fib(2)
    for _ in range(n - 2):
        a, b = b, a + b
    return b if n >= 2 else a


print(fib_naive(20), calls)   # 출력: 6765 13529
print(fib_top_down(20))       # 출력: 6765
print(fib_bottom_up(20))      # 출력: 6765
print(fib_two_vars(20))       # 출력: 6765
print(fib_bottom_up(90))      # 출력: 2880067194370816120

1. 점화식을 그대로 재귀로 옮긴 버전입니다. 답은 맞지만 fib(20)에 13,529번이나 호출됩니다. calls는 호출 횟수를 세기 위한 변수입니다.
2. Top-down 방식입니다. memo 딕셔너리(값을 이름표로 찾는 해시맵)에 답을 적어 두고, 이미 있으면 바로 돌려줍니다. 다만 n이 1000을 넘으면 재귀가 너무 깊어져 RecursionError가 날 수 있습니다.
3. Bottom-up 방식입니다. dp 표를 작은 i부터 채우므로 재귀가 없습니다. fib(90)처럼 큰 값도 바로 구합니다.
4. dp[i]를 구할 때 직전 두 값만 필요하다는 점을 이용해, 표 대신 변수 두 개만 씁니다.

시간복잡도와 공간복잡도

피보나치는 n만 정해지면 계산량이 정해지므로 최선, 평균, 최악이 같습니다.

방법	시간 (최선/평균/최악)	추가 공간
그냥 재귀	O(2^n)	O(n) (재귀 호출 스택)
Top-down (메모이제이션)	O(n)	O(n) (메모 + 재귀 스택)
Bottom-up (표)	O(n)	O(n) (dp 표)
Bottom-up (변수 두 개)	O(n)	O(1)

• 그냥 재귀는 호출이 매번 두 갈래로 나뉘어 O(2^n)입니다. 더 정확히는 약 1.618^n배씩 늘어나지만, 어쨌든 n에 대해 지수적으로 커집니다.
• DP를 쓰면 fib(1)부터 fib(n)까지 각각 한 번씩만 계산하므로 O(n)입니다.
• 표기법이 낯설다면 시간 복잡도 글을 참고하세요.

활용 예

• 최장 증가 수열 (LIS): "i번째 값으로 끝나는 가장 긴 증가 수열의 길이"를 표에 저장합니다.
• 비트마스크: "어떤 도시들을 방문했는지"를 정수 하나로 표현해 DP 표의 칸 번호로 씁니다. (외판원 순회 문제)
• 그 밖에 계단 오르기, 배낭 문제, 최소 동전 개수처럼 "작은 경우의 답을 조합해 큰 경우의 답을 만드는" 문제에 두루 쓰입니다.

정리

개념	비전공자 버전 요약
동적 계획법 (DP)	큰 문제를 작은 문제로 쪼개고, 푼 답은 노트에 적어 재사용
겹치는 부분 문제	같은 작은 문제가 여러 번 등장하는 구조
최적 부분 구조	작은 문제의 답을 조합하면 큰 문제의 답이 되는 구조
메모이제이션	한 번 계산한 답을 저장해 두고 다시 계산하지 않기
Bottom-up	작은 문제부터 표를 차례로 채우기 (반복문)
Top-down	큰 문제에서 출발해 필요할 때 작은 문제 풀기 (재귀)
점화식	앞의 답들로 다음 답을 만드는 규칙

참고: 나무위키 - 동적 계획법