Ch.10 다이나믹 프로그래밍
Bottom-Up Tabulation — dp 배열 채우기
재귀 없이도 DP가 된다?
메모이제이션은 재귀 깊이 제한이 걸립니다. Bottom-Up은 반복문으로 작은 문제부터 순서대로 풀어 이 한계를 넘깁니다.
재귀 없이 어떻게 하위 문제의 결과를 쌓아올릴 수 있을까?
dp 배열을 만들고, 인덱스 0부터 차례로 채워나가면 됩니다.
핵심 개념
타뷸레이션
dp 배열을 작은 인덱스부터 반복문으로 채워나가는 방식
공간 최적화
dp 배열 대신 변수 몇 개만으로 결과를 구하는 기법
핵심 내용
Bottom-Up은 가장 작은 문제부터 순서대로 답을 쌓아갑니다
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib(40)) # 102334155
print(fib(1000)) # 스택 오버플로 없음!재귀가 없으므로 스택 오버플로 걱정이 없습니다. n=10만이어도 문제없이 동작합니다
fib(6)을 Bottom-Up으로 한 줄씩 추적합니다
작은 인덱스부터 차례로 채워서 dp[6] = 8을 구했습니다
피보나치에서 dp[i]를 구할 때 필요한 건 직전 두 값뿐입니다
def fib(n):
if n <= 1:
return n
prev2, prev1 = 0, 1 # dp[i-2], dp[i-1]
for i in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
# 공간: O(n) → O(1)!공간 최적화 패턴: • dp[i]가 dp[i-1], dp[i-2]에만 의존 → 변수 2개 • dp[i]가 dp[i-1]에만 의존 → 변수 1개 • 2D dp에서 현재 행이 이전 행에만 의존 → 1D 배열 면접에서 공간 최적화까지 하면 보너스 점수!
시간 O(n), 공간 O(1). 이것이 피보나치의 최적 해법입니다
Bottom-Up을 설계할 때 이 순서를 따르세요
Bottom-Up 설계 3단계: 1️⃣ dp 배열의 크기와 의미 결정 → dp = [0] * (n+1), dp[i]의 정의 2️⃣ 기저 사례 초기화 → dp[0] = ?, dp[1] = ? 3️⃣ 채우는 순서 결정 → 작은 인덱스 → 큰 인덱스 (보통 순방향)
이 3단계를 면접에서 소리 내어 진행하면 구조적 사고력을 어필할 수 있습니다
대부분의 1D DP는 순방향 for문으로 채웁니다. 2D는 행→열 순서가 일반적입니다
두 방식을 종합적으로 비교합니다
Top-Down (메모이제이션): • 재귀 기반 — 직관적 • 필요한 부분문제만 계산 • 재귀 깊이 제한 있음 Bottom-Up (타뷸레이션): • 반복문 기반 — 효율적 • 모든 부분문제를 순서대로 계산 • 공간 최적화 가능 • 스택 오버플로 없음
면접 전략: Top-Down으로 빠르게 풀고, 면접관이 요구하면 Bottom-Up + 공간 최적화로 전환
Bottom-Up 피보나치에서 공간을 O(1)로 최적화하려면?
Bottom-Up은 Top-Down보다 항상 더 효율적이다
Bottom-Up 완전 정복!
핵심 용어
타뷸레이션
dp 배열을 반복문으로 작은 인덱스부터 채우기
공간 최적화
dp 배열 대신 변수 몇 개만으로 결과 계산
정리 노트
Bottom-Up Tabulation — dp 배열 채우기
구현 패턴
- 기본
- dp 배열 선언 → 기저 사례 → for문으로 채우기
- 공간 최적화
- dp[i-1], dp[i-2]만 필요하면 변수 2개로 충분
Top-Down vs Bottom-Up
- Top-Down
- 재귀 + 캐싱 — 직관적, 재귀 깊이 제한
- Bottom-Up
- 반복문 + dp 배열 — 효율적, 공간 최적화 가능
면접에서 공간 최적화를 먼저 제안하면 '시니어 레벨'이라는 인상을 줍니다!
핵심 정리
- 1Bottom-Up = 반복문 + dp 배열
- 2작은 문제부터 순서대로 채워나감
- 3공간 최적화로 O(n) → O(1) 가능
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작