📌 다이나믹 프로그래밍(DP) 이란?

흔히 DP라고 불리는 동적 계획법이란 큰 문제를 더 작은 하위 문제들로 나누어 해결하고, 그 결과를 재사용하여 전체 문제를 해결하는 알고리즘 설계 기법이다. 한 번 푼 문제를 다시 푸는 비효율적인 행위를 방지해 알고리즘을 개선시킬 수 있다.
주로 최적화 문제나 조합적 문제를 효율적으로 해결하기 위해 사용된다.

DP를 적용하려면 다음 2가지 조건을 만족해야 한다.

1. 중복되는 부분 문제(Overlapping Subproblems)

• 동일한 작은 문제가 여러 번 반복해서 나타나는 성질.

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

• 문제의 최적 해결 방법이 그 하위 문제의 최적 해결 방법으로 구성되는 성질.

두 조건을 만족하는 대표적인 예시로 피보나치 수열이 있다.

$f(n) = f(n-1) + f(n-2)$
위 점화식을 가진 피보나치 수열을 계산해보자.

1, 2, 1+2, 2+(1+2), (1+2)+(2+(1+2)) ...

다음과 같이 이전에 해결했던 동일한 부분 문제가 중복되어 나타난다. 이럴 때 DP를 통해 한 번 계산했던 값을 저장해 다음 문제를 해결할 때 재활용할 수 있게 된다.

---

📌 구현 방법

메모이제이션(Memoization)

• 하향식 접근 방식(Top-Down)으로 재귀적으로 문제를 푸는 과정에서 이미 계산한 하위 문제의 결과를 캐싱하여 중복 계산을 방지한다.

타뷸레이션(Tabulation)

• 상향식 접근 방식(Bottum-Up)으로 작은 문제부터 해결해 가며, 계산 결과를 테이블에 저장하여 큰 문제를 해결한다.

메모이제이션과 타뷸레이션의 차이를 확인하기 위해 DP를 통해 해결할 수 있는 대표적인 문제인 피보나치 수열을 구현해보자.

메모이제이션

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(10))

• 재귀적으로 호출하며, 필요한 때만 하위 문제를 계산한다.
• 하위 문제가 이미 계산된 경우, 저장된 값을 재사용한다.

타뷸레이션

def fib(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]

print(fib(10))

• 작은 문제부터 반복적으로 계산하여 테이블을 채운다.

그렇다면 언제 어떤 방법을 사용해야 할까?

• 문제 크기가 크고 깊은 재귀 호출이 필요할 때: 타뷸레이션(스택 오버플로우 방지).
• 점화식이 직관적이고 재귀적으로 문제를 풀기 쉬울 때: 메모이제이션(코드 작성이 간단하다).
• 메모리 최적화가 필요하거나 하위 문제 일부만 계산하면 되는 경우: 메모이제이션(효율적이다).