테이블화: Bottom-Up DP

"메모이제이션은 아래로 재귀하고 기억해. 테이블화는 뒤집어: 가장 작은 답에서 시작해 위로 지어, 큰 답이 떨어질 때까지 테이블을 채워. 같은 DP, 반대 방향, 재귀 전혀 없음."

아래로 재귀하는 대신 위로 짓기

테이블화 (tabulation)는 bottom-up 동적 계획법이야. 큰 문제에서 시작해 base case 로 재귀하는 대신, base case 에서 시작해 테이블을 앞으로 반복 채워, 이미 채운 항목으로 각 항목을 계산하며, 원한 답에 닿을 때까지. 재귀 없음 — 테이블 위 평범한 루프야. base case 가 씨앗; 마지막 칸이 결과. 피보나치 bottom-up: dp[0]=0, dp[1]=1, 그다음 dp[i] = dp[i-1] + dp[i-2] 를 n 까지 루프.

새로운 도전 하나: 채우는 순서

테이블화가 들이는 함정은 순서야: 항목을 계산할 때 그게 의존하는 모든 게 이미 거기 있도록 테이블을 채워야 해. 피보나치엔 자명하게 왼쪽에서 오른쪽. 2D DP (편집 거리 같은) 엔, 행별로, 또는 의존성을 존중하는 어떤 순서로든 채우기. 메모이제이션은 순서를 자동으로 다뤘어 (재귀가 의존성을 필요할 때 계산); 테이블화는 네가 생각하게 해. 그게 거래야: 테이블화는 앞에 설계 노력을 더 요구해, 재귀를 잃는 대가로.

테이블화 = bottom-up DP: base case 를 씨앗으로, 그다음 답에 닿을 때까지 테이블을 앞으로 반복 채움 (각 항목을 이미 계산된 것으로). 재귀 없음 (스택 한계 없음), 종종 더 빠름, 근데 의존성을 존중하는 채우기 순서를 골라야 하고 — 안 필요한 것도 모든 상태를 계산해.

공간 승리: 필요한 것만 유지

테이블화가 메모이제이션이 쉽게 못 맞추는 아름다운 최적화를 열어. 종종 각 테이블 항목이 마지막 행이나 마지막 몇 칸에만 의존해 — 그래서 전체 테이블이 메모리에 필요 없고, 그 슬라이딩 윈도우만. 피보나치는 앞 두 값만 필요해, 그래서 전체 O(n) 테이블이 변수 둘, O(1) 공간으로 무너져. O(n×m) 격자가 필요해 보이는 많은 2D DP 가 사실 앞 행만 필요해, 공간을 O(m) 으로 떨궈. '마지막 K 칸에만 의존해' 를 알아보는 게 DP 공간 비용이 극적으로 줄어드는 법 — 매번 찾을 가치 있는 반복 트릭.

메모이제이션이냐 테이블화냐?

같은 답을 계산해; 제약으로 골라. 메모이제이션: 쓰기 쉬움 (재귀 캐시), 지연 (필요한 상태만), 근데 재귀-깊이 제한. 테이블화: 재귀 한계 없음, 종종 더 빠름, 위 공간 최적화 가능, 근데 채우기 순서를 설계해야 하고 모든 상태를 계산. 흔한 작업 흐름: 메모이제이션으로 프로토타입해 점화식을 맞게 하고, 깊이-안전이나 공간 절약이 필요하면 테이블화로 변환. 같은 DP, 상황에 골라.

피파의 고백

큰 입력에 재귀 한계를 계속 치는 메모이제이션 DP 가 있었어. 아빠가 방향 돌리기 전에 한계를 올리려 했어 (재귀 트랙의 함정). bottom-up 테이블로 변환해 — 재귀 없음, 한계 없음. 다시 쓰는 게 채우기 순서를 생각하게 강제했어, 전엔 한 적 없는, 그때 DP 가 진짜 딸깍했어: 메모이제이션이 의존성 구조를 나한테 감추고 있었어. 테이블화가 재귀가 찾길 그냥 믿는 게 아니라 계산의 모양을 보게 했어.

Code

테이블화, 공간 트릭, 그리고 동전 교환·python

# 테이블화: base case 에서 답을 위로 짓기, 재귀 없음.
def fib_table(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1            # base case 가 테이블 씨앗
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 각 항목을 이미 채운 것으로
    return dp[n]

# 공간-최적화: 각 항목이 마지막 둘만 필요, 그래서 테이블 버림.
def fib_two_vars(n):              # O(n) 대신 O(1) 공간
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b           # 두 값의 윈도우를 앞으로 밀어
    return a

print(fib_table(10), fib_two_vars(10))   # 55 55

# 동전 교환, bottom-up: dp[a] = 금액 a 만드는 최소 동전.
def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount      # dp[0]=0; 나머지 미지
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a-c] + 1)   # 순서대로 앞으로 채움
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 3, 4], 6))   # 2 — 메모이제이션 버전이랑 같은 답

Exercise

'계단 오르기' DP (ways(n) = ways(n-1) + ways(n-2)) 를 메모이제이션에서 bottom-up 테이블화로 변환해. 채우기 순서랑 base case 를 써. 그다음 O(1) 로 공간-최적화해 — 전체 테이블 대신 뭘 유지하고, 왜 그게 충분해?

Hint

테이블화: dp[0]=1, dp[1]=1, 그다음 i 를 2 부터 n 까지: dp[i]=dp[i-1]+dp[i-2], 왼쪽에서 오른쪽 (각자 더 앞 칸에만 의존). 공간-최적화: dp[i] 가 앞 두 값만 필요하니, 변수 둘 (a, b) 을 유지하고 앞으로 밀어 — O(1) 공간, 마지막 둘보다 오래된 건 다시 안 읽으니까.

아래로 재귀하는 대신 위로 짓기

새로운 도전 하나: 채우는 순서

공간 승리: 필요한 것만 유지

메모이제이션이냐 테이블화냐?

피파의 고백

Code

External links

Exercise

Progress

댓글 0