동적 계획법 DP 입문: 메모이제이션과 효율적 문제 해결

알고리즘의 난이도가 올라갈수록 우리는 '중복'이라는 거대한 벽에 부딪힙니다. 같은 계산을 수천 번, 수만 번 반복하며 CPU 자원을 낭비하는 비효율을 해결하기 위해 탄생한 기법이 바로 동적 계획법(Dynamic Programming, DP)입니다. DP는 한 번 구한 정답을 메모리에 기록해두었다가 필요할 때 꺼내 쓰는 '똑똑한 기록장' 전략을 취합니다. 본 포스팅에서는 DP의 핵심인 메모이제이션(Memoization)의 원리부터 하향식과 상향식 접근의 차이점까지 2,500자 이상의 밀도 있는 해설로 정리해 보겠습니다.

1. 동적 계획법(DP)의 탄생 배경: 피보나치의 교훈

우리가 중학교 수학 시간에 배운 피보나치 수열은 DP의 필요성을 가장 잘 보여줍니다. 단순 재귀로 피보나치 수열을 구현하면 $F(5)$를 구하기 위해 $F(3)$을 두 번, $F(2)$를 세 번이나 중복해서 계산합니다. 숫자가 커질수록 이 중복은 기하급수적으로 늘어나 $O(2^n)$이라는 파멸적인 복잡도를 가집니다. DP는 이러한 중복되는 부분 문제(Overlapping Subproblems)를 발견하고, 단 한 번만 계산하여 저장하는 방식으로 문제를 해결합니다.

1-1. 최적 부분 구조(Optimal Substructure)의 이해

DP가 성립하기 위한 또 다른 조건은 큰 문제의 최적해가 작은 문제들의 최적해로부터 구성될 수 있어야 한다는 점입니다. 이 성질 덕분에 우리는 문제를 작은 단위로 쪼개고, 그 결과를 누적하여 전체 문제를 해결할 수 있습니다. 이는 분할 정복과 유사해 보이지만, 부분 문제가 서로 겹친다는 점에서 결정적인 차이를 보입니다.

2. 메모이제이션(Memoization) vs 타뷸레이션(Tabulation)

DP를 구현하는 방식은 크게 두 가지로 나뉩니다. 두 방식은 논리적으로 동일한 결과를 내지만, 컴퓨터 메모리를 사용하는 방식과 실행 흐름에서 뚜렷한 개성을 가집니다.

2-1. 하향식(Top-Down)과 메모이제이션

큰 문제를 해결하기 위해 작은 문제를 호출하는 방식입니다. 주로 재귀 함수와 함께 사용되며, 이미 계산된 값을 배열이나 해시 테이블에 저장하는 행위를 '메모이제이션'이라고 부릅니다. 필요한 부분 문제만 계산한다는 장점이 있지만, 재귀 깊이가 깊어지면 시스템 스택에 부담을 줄 수 있습니다.

2-2. 상향식(Bottom-Up)과 타뷸레이션

작은 문제부터 차례대로 정답을 구해 나가며 테이블을 채우는 방식입니다. 반복문을 사용하여 구현하며, 이를 '타뷸레이션'이라고 합니다. 재귀 호출의 오버헤드가 없고 실행 속도가 안정적이라 실무와 코딩 테스트에서 가장 선호되는 방식입니다.

3. DP 점화식 설계의 3단계 프로세스

DP 문제를 마주했을 때 가장 어려운 것은 '어떤 값을 저장할 것인가'입니다. 이를 위한 표준적인 접근 단계는 다음과 같습니다.

상태 정의: dp[i]가 무엇을 의미하는지 문장으로 명확히 정의합니다. (예: i원까지의 최소 동전 개수)
점화식 도출: dp[i]와 dp[i-1] 혹은 다른 상태들 간의 논리적 관계를 수식으로 세웁니다.
기저 사례(Base Case) 설정: 가장 작은 단위(예: dp[0], dp[1])의 초기값을 설정합니다.

4. DP의 시간 및 공간 복잡도 분석

DP를 사용하면 지수 시간 복잡도를 다항 시간($O(N)$ 또는 $O(N^2)$ 등)으로 획기적으로 줄일 수 있습니다. 피보나치의 경우 $O(2^n)$에서 $O(N)$으로 개선됩니다. 다만, 값을 저장하기 위한 추가적인 공간이 필요하므로 공간 복잡도는 $O(N)$이 됩니다. 최근에는 이전의 모든 상태가 아닌 직전 상태만 저장하는 방식으로 공간 복잡도를 최적화하는 기법도 널리 쓰입니다.


# 피보나치 수열 - 상향식 DP 구현 (Python)
def fibo_bottom_up(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

[동적 계획법 입문 핵심 요약]
1. 철학: 중복 계산을 피하기 위해 부분 문제의 해를 저장하고 재사용합니다.
2. 구현: 재귀 기반의 하향식(메모이제이션)과 반복문 기반의 상향식(타뷸레이션)이 있습니다.
3. 성공 열쇠: 문제의 핵심 규칙을 찾아내어 논리적인 점화식을 설계하는 것이 가장 중요합니다.

tech-korea