dynamic programming(memoization vs tabulation)이란 무엇인가요?

Question

Accepted Answer

**Dynamic programming(DP, 동적 계획법)**은 **겹치는 부분 문제(overlapping subproblems)**와 **최적 부분 구조(optimal substructure)**를 가진 문제를, 각 부분 문제를 한 번 계산하고 결과를 재사용하여 해결합니다. 두 가지 방식은 **memoization**(하향식)과 **tabulation**(상향식)입니다.

## 개념

단순한 재귀는 같은 부분 문제를 지수적으로 재계산합니다. DP는 그것을 캐시하여 지수적 작업을 다항 시간으로 축소합니다.

## Memoization (하향식)

```python
from functools import lru_cache

@lru_cache(maxsize=None)               # 결과를 자동으로 캐시
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)     # 각 n을 한 번만 계산
```

## Tabulation (상향식)

```python
def fib_table(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])  # base case부터 쌓아 올림
    return dp[n]
```

## Memoization vs tabulation

| | Memoization | Tabulation |
|---|------------|------------|
| 방향 | 하향식 재귀 | 상향식 반복 |
| 계산 | 필요한 상태만 | 모든 상태 |
| 위험 | 스택 오버플로 | 없음 |
| 공간 | 줄일 수 있음 | 흔히 O(1) 행으로 줄일 수 있음 |

## 복잡도

피보나치: 단순한 O(2ⁿ)에서 **O(n)** 시간, O(n)(또는 O(1)) 공간으로.

## 언제 사용하나 / 함정

부분 문제가 **겹칠 때** DP를 사용하세요. 상태와 점화식을 신중히 정의하세요 — 그것이 어려운 부분입니다. 부분 문제가 겹치지 않으면 평범한 분할 정복으로 충분합니다.

## 왜 중요한가

DP는 다루기 힘든 지수 문제 — 최단 경로, edit distance, knapsack — 를 효율적인 것으로 바꿉니다.

상태와 점화식을 식별하는 기술은 알고리즘 면접에서 가장 가치 있는 것 중 하나입니다.

diff 도구부터 생물정보학 서열 정렬까지 실제 시스템의 기반이 됩니다.

	Memoization	Tabulation
방향	하향식 재귀	상향식 반복
계산	필요한 상태만	모든 상태
위험	스택 오버플로	없음
공간	줄일 수 있음	흔히 O(1) 행으로 줄일 수 있음