통합 요약노트
Ch.10 다이나믹 프로그래밍
Memoization, Tabulation, 1D/2D DP, 문자열 DP
이 챕터의 내용
DP란? — 중복 부분문제와 최적 부분구조
한 번 계산한 결과를 저장해서 재사용 — 이것이 Dynamic Programming의 핵심입니다.
면접에서 가장 많이 나오는 주제, Dynamic Programming을 시작합니다
피보나치 수열을 재귀로 풀면 어떤 일이 벌어질까요?
fib(40)을 구하려면 fib(39) + fib(38)을 호출하고, fib(39)는 또 fib(38) + fib(37)을 호출합니다. fib(38)이 이미 2번 계산됩니다!
- DP = 중복 부분문제 + 최적 부분구조
- 순수 재귀 O(2^n) → DP 적용 시 O(n)
- Top-Down(메모이제이션)과 Bottom-Up(타뷸레이션) 두 방식
Top-Down Memoization — 재귀 + 캐싱
메모이제이션(Memoization) — 함수 호출 결과를 캐싱하여 같은 입력이 들어오면 즉시 반환합니다.
가장 직관적인 방법: 딕셔너리에 결과를 저장합니다
memo 딕셔너리가 이미 계산한 값을 기억합니다. fib(38)이 두 번째 호출되면 즉시 반환!
fib(5)를 메모이제이션으로 한 줄씩 추적합니다
- 메모이제이션 = 재귀 + 결과 캐싱
- lru_cache 데코레이터로 한 줄 구현
- O(2^n) → O(n)으로 극적 최적화
Bottom-Up Tabulation — dp 배열 채우기
dp 배열을 만들고, 인덱스 0부터 차례로 채워나가면 됩니다.
Bottom-Up은 가장 작은 문제부터 순서대로 답을 쌓아갑니다
재귀가 없으므로 스택 오버플로 걱정이 없습니다. n=10만이어도 문제없이 동작합니다
fib(6)을 Bottom-Up으로 한 줄씩 추적합니다
- Bottom-Up = 반복문 + dp 배열
- 작은 문제부터 순서대로 채워나감
- 공간 최적화로 O(n) → O(1) 가능
1D DP — Climbing Stairs, House Robber
dp[i] = dp[i-1] + dp[i-2] — 한 줄의 점화식이 문제를 풀어줍니다.
Climbing Stairs (LeetCode #70) n계단을 1칸 또는 2칸씩 오르는 방법의 수
이건 피보나치 수열과 완전히 같은 구조입니다!
세 가지 버전으로 구현해봅시다
- Climbing Stairs = 피보나치 변형
- House Robber = 선택/비선택 패턴
- 공간 최적화: dp 배열 → 변수 2개
2D DP — Unique Paths, 0/1 Knapsack
dp[i][j] — 2차원 테이블의 각 칸을 채우면 답이 보입니다.
Unique Paths (LeetCode #62) m×n 격자에서 경로의 수를 구합니다
2D dp 테이블을 채우고 공간 최적화까지 해봅시다
시간 O(m×n), 공간 O(n). 2D를 1D로 압축하는 롤링 배열 기법!
- Unique Paths: dp[i][j] = 위 + 왼쪽
- 0/1 Knapsack: 넣거나/안 넣거나 선택
- 2D → 1D 공간 최적화 (롤링 배열, 역순)
문자열 DP — Edit Distance, LCS
dp[i][j] = 첫 번째 문자열의 i글자와 두 번째 문자열의 j글자 사이의 최소 편집 거리
Edit Distance (LeetCode #72) 두 문자열 사이의 최소 편집 횟수
코드로 구현하고 dp 테이블을 확인합니다
시간 O(m×n), 공간 O(m×n). 1D 최적화로 O(n) 공간도 가능합니다
- Edit Distance: 삽입·삭제·교체 최소 횟수
- LCS: 순서 유지 최장 공통 부분수열
- 문자열 DP = dp[i][j] + 글자 비교 전이
면접실전 — DP 5단계 프레임워크
상태 정의 → 점화식 → 기저 사례 → 순서 → 최적화 — 이 5단계가 모든 DP 문제의 로드맵입니다.
어떤 DP 문제든 이 5단계로 풀 수 있습니다
면접에서 이 5단계를 소리 내어 설명하면 면접관에게 강한 인상을 줍니다
Coin Change (LeetCode #322) 5단계로 풀어봅시다
- DP 5단계: 상태 → 점화식 → 기저 → 순서 → 최적화
- Coin Change: 그리디 실패 시 DP가 답
- LIS: O(n²) DP → O(n log n) 이진 탐색
챕터10 종합퀴즈 — Dynamic Programming
종합 퀴즈로 약점을 발견하고, 부족한 부분은 다시 복습합시다.
챕터 10 Dynamic Programming 종합 퀴즈를 시작합니다
DP가 분할정복과 다른 핵심 차이점은?
순수 재귀 피보나치 fib(n)의 시간 복잡도는?
- DP = 중복 부분문제 + 최적 부분구조
- Top-Down(메모이제이션) vs Bottom-Up(타뷸레이션)
- 1D, 2D, 문자열 DP 패턴 정복
- 5단계 프레임워크로 면접 실전 대비 완료
핵심 용어 모음
Dynamic Programming
하위 문제의 결과를 저장·재사용하여 효율적으로 푸는 기법
중복 부분문제
같은 하위 문제가 여러 번 반복 계산되는 구조
최적 부분구조
전체 최적해가 부분 문제의 최적해로 구성되는 성질
메모이제이션
함수 결과를 딕셔너리에 저장·재사용
lru_cache
Python 내장 자동 메모이제이션 데코레이터
타뷸레이션
dp 배열을 반복문으로 작은 인덱스부터 채우기
공간 최적화
dp 배열 대신 변수 몇 개만으로 결과 계산
점화식
dp[i]를 이전 값들로 표현하는 관계식
1D DP
1차원 배열 하나로 해결하는 DP 패턴
2D DP
두 인덱스 (i, j)로 상태를 표현하는 DP
0/1 Knapsack
각 물건을 넣거나/안 넣거나 선택하는 최적화
Edit Distance
삽입·삭제·교체로 문자열을 바꾸는 최소 횟수
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기