Ch.10 다이나믹 프로그래밍
챕터10 종합퀴즈 — Dynamic Programming
DP 마스터 최종 시험!
지금까지 배운 DP의 모든 것을 총정리합니다. 중복 부분문제부터 LIS까지, 얼마나 이해하고 있는지 확인해봅시다.
7개 섹션의 내용을 모두 기억하고 있을까?
종합 퀴즈로 약점을 발견하고, 부족한 부분은 다시 복습합시다.
핵심 내용
챕터 10 Dynamic Programming 종합 퀴즈를 시작합니다
출제 범위: • DP 개념: 중복 부분문제, 최적 부분구조 • Top-Down (메모이제이션) vs Bottom-Up (타뷸레이션) • 1D DP: Climbing Stairs, House Robber • 2D DP: Unique Paths, 0/1 Knapsack • 문자열 DP: Edit Distance, LCS • 면접 실전: Coin Change, LIS
DP가 분할정복과 다른 핵심 차이점은?
순수 재귀 피보나치 fib(n)의 시간 복잡도는?
Bottom-Up 방식의 장점이 아닌 것은?
House Robber에서 nums = [2, 1, 1, 2]일 때 최대 금액은?
0/1 Knapsack을 1D로 최적화할 때 무게를 역순으로 순회하는 이유는?
LCS("abc", "ac")의 길이는?
Edit Distance에서 두 글자가 같을 때 dp[i][j]의 값은?
coinChange([2], 3)의 결과는?
[3, 1, 2, 4]에서 LIS의 길이는?
모든 재귀 문제에 DP를 적용할 수 있다
Climbing Stairs 문제는 피보나치 수열과 동일한 점화식이다
DP 5단계 프레임워크의 첫 번째는 '점화식 도출'이다
Edit Distance에서 가능한 연산은 삽입, 삭제, 교체 3가지다
DP 마스터 달성!
정리 노트
챕터10 종합 정리 — Dynamic Programming
DP 핵심 개념
- DP 조건
- 중복 부분문제 + 최적 부분구조
- Top-Down
- 재귀 + memo — 직관적, 재귀 깊이 제한
- Bottom-Up
- 반복문 + dp 배열 — 효율적, 공간 최적화 가능
핵심 문제 & 점화식
- Climbing Stairs
- dp[i] = dp[i-1] + dp[i-2]
- House Robber
- dp[i] = max(dp[i-1], dp[i-2]+nums[i])
- Unique Paths
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Knapsack
- dp[i][w] = max(skip, take)
- Edit Distance
- 같으면 dp[i-1][j-1], 다르면 1+min(3방향)
- LCS
- 같으면 dp[i-1][j-1]+1, 다르면 max(2방향)
- Coin Change
- dp[i] = min(dp[i-coin]+1)
- LIS
- dp[i] = max(dp[j]+1) → O(n log n) 이진탐색
DP는 패턴을 외우는 것보다 '왜 이 점화식이 성립하는지' 이해하는 것이 핵심!
핵심 정리
- 1DP = 중복 부분문제 + 최적 부분구조
- 2Top-Down(메모이제이션) vs Bottom-Up(타뷸레이션)
- 31D, 2D, 문자열 DP 패턴 정복
- 45단계 프레임워크로 면접 실전 대비 완료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작