Ch.10 다이나믹 프로그래밍
면접실전 — DP 5단계 프레임워크
면접에서 DP 문제를 체계적으로 푸는 법
면접관이 DP 문제를 냈습니다. 점화식이 바로 떠오르지 않습니다. 패닉할 필요 없습니다 — 5단계 프레임워크를 따르면 됩니다.
DP 문제는 너무 다양한데, 어떻게 체계적으로 접근할 수 있을까?
상태 정의 → 점화식 → 기저 사례 → 순서 → 최적화 — 이 5단계가 모든 DP 문제의 로드맵입니다.
핵심 개념
DP 프레임워크
DP 문제를 체계적으로 풀기 위한 5단계 접근법
Coin Change
주어진 동전으로 금액을 만드는 최소 동전 수 문제
LIS
배열에서 순서를 유지하며 증가하는 가장 긴 부분수열
핵심 내용
어떤 DP 문제든 이 5단계로 풀 수 있습니다
DP 5단계 프레임워크: 1️⃣ 상태 정의 — dp[i]가 무엇을 의미하는지 정의 2️⃣ 점화식 — dp[i]를 이전 값들로 표현 3️⃣ 기저 사례 — dp[0], dp[1] 등 초기값 설정 4️⃣ 순서 — 어떤 순서로 dp를 채울지 결정 5️⃣ 최적화 — 공간 최적화, 시간 최적화 검토
면접에서 이 5단계를 소리 내어 설명하면 면접관에게 강한 인상을 줍니다
Coin Change (LeetCode #322) 5단계로 풀어봅시다
문제: 동전 종류 coins = [1, 5, 10, 25] 금액 amount = 30일 때 최소 동전 수는? 1️⃣ 상태: dp[i] = 금액 i를 만드는 최소 동전 수 2️⃣ 점화식: dp[i] = min(dp[i - coin] + 1) for coin in coins 3️⃣ 기저: dp[0] = 0 (0원 = 동전 0개) 4️⃣ 순서: 1부터 amount까지 순방향 5️⃣ 최적화: 이미 1D — 추가 최적화 불필요
def coinChange(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# coins = [1, 5, 10, 25], amount = 30
# dp[30] = 2 (25 + 5)시간 O(amount × len(coins)), 공간 O(amount)
LIS (LeetCode #300) 가장 긴 증가 부분수열의 길이
예시: [10, 9, 2, 5, 3, 7, 101, 18] LIS = [2, 3, 7, 101] → 길이 4 DP 풀이 (O(n²)): 1️⃣ dp[i] = nums[i]로 끝나는 LIS의 길이 2️⃣ dp[i] = max(dp[j] + 1) for j < i if nums[j] < nums[i] 3️⃣ dp[i] = 1 (자기 자신만으로 길이 1) 4️⃣ i를 0부터 n-1까지 5️⃣ 이진 탐색으로 O(n log n) 가능
O(n²) DP와 O(n log n) 이진 탐색 풀이
# O(n²) DP 풀이
def lengthOfLIS(nums: list[int]) -> int:
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# [10, 9, 2, 5, 3, 7, 101, 18]
# dp = [1, 1, 1, 2, 2, 3, 4, 4]
# 답: 4# O(n log n) 이진 탐색 풀이
import bisect
def lengthOfLIS(nums: list[int]) -> int:
tails = [] # 각 길이의 LIS 끝값 중 최소
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num) # 새로운 최장
else:
tails[pos] = num # 더 작은 끝값으로 교체
return len(tails)
# tails 변화: [10] → [9] → [2] → [2,5]
# → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
# 답: 4면접에서 O(n²)로 먼저 풀고, O(n log n) 최적화를 제시하면 합격 확률 UP!
DP 면접에서 반드시 기억할 전략
면접 DP 전략: 1. "이 문제에 DP를 쓸 수 있는 이유"를 먼저 말한다 → 중복 부분문제 + 최적 부분구조 언급 2. 5단계 프레임워크를 소리 내어 진행 → 상태 정의부터 시작 3. Top-Down으로 빠르게 구현 → Bottom-Up + 공간 최적화로 follow-up 4. 시간/공간 복잡도를 정확히 분석 → (부분문제 수) × (문제당 시간)
DP는 연습량이 실력입니다. 패턴을 익히면 새로운 문제도 풀 수 있습니다
coinChange([1, 5, 11], 15)의 결과는?
LIS의 이진 탐색 풀이의 시간 복잡도는 O(n log n)이다
면접 실전 준비 완료!
핵심 용어
DP 프레임워크
상태 → 점화식 → 기저 → 순서 → 최적화
Coin Change
최소 동전 수로 금액 만들기
LIS
최장 증가 부분수열
정리 노트
면접실전 — DP 5단계 프레임워크
5단계 프레임워크
- 1단계
- 상태 정의 — dp[i]의 의미
- 2단계
- 점화식 — dp[i]와 이전 값의 관계
- 3단계
- 기저 사례 — 초기값 설정
- 4단계
- 순서 — dp 배열 채우는 방향
- 5단계
- 최적화 — 공간/시간 개선
핵심 문제
- Coin Change
- dp[i] = min(dp[i-coin]+1) — O(amount×coins)
- LIS
- DP O(n²) → 이진탐색 O(n log n)
Coin Change는 그리디가 실패하는 대표적 케이스 — 면접에서 자주 언급됩니다!
시각 자료
핵심 정리
- 1DP 5단계: 상태 → 점화식 → 기저 → 순서 → 최적화
- 2Coin Change: 그리디 실패 시 DP가 답
- 3LIS: O(n²) DP → O(n log n) 이진 탐색
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작