Ch.10 다이나믹 프로그래밍
DP란? — 중복 부분문제와 최적 부분구조
같은 계산을 왜 반복하는가?
피보나치 수열을 재귀로 구현했더니 n=40에서 이미 수 초가 걸립니다. 그런데 단 한 줄을 추가하면 0.001초로 줄어듭니다.
재귀 트리를 그려보면, 같은 값을 수십 번씩 다시 계산하고 있었습니다.
한 번 계산한 결과를 저장해서 재사용 — 이것이 Dynamic Programming의 핵심입니다.
핵심 개념
Dynamic Programming
복잡한 문제를 작은 하위 문제로 나누고, 결과를 저장하여 재사용하는 기법
중복 부분문제
같은 하위 문제가 여러 번 반복되는 구조
최적 부분구조
전체 최적해가 부분 최적해로 구성되는 성질
핵심 내용
면접에서 가장 많이 나오는 주제, Dynamic Programming을 시작합니다
피보나치 수열을 재귀로 풀면 어떤 일이 벌어질까요?
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(5)) # 5 — 빠름
print(fib(40)) # 102334155 — 매우 느림!fib(40)을 구하려면 fib(39) + fib(38)을 호출하고, fib(39)는 또 fib(38) + fib(37)을 호출합니다. fib(38)이 이미 2번 계산됩니다!
fib(5)의 재귀 트리를 시각화해봅시다
fib(5) 호출 시 총 15번의 함수 호출 발생: • fib(3) — 2번 중복 • fib(2) — 3번 중복 • fib(1) — 5번 중복 • fib(0) — 3번 중복
n이 커질수록 중복은 지수적으로 폭발합니다. fib(40)은 약 3억 번의 호출을 합니다
이렇게 같은 하위 문제가 반복 계산되는 것을 중복 부분문제(Overlapping Subproblems)라 합니다
DP가 성립하려면 한 가지 조건이 더 필요합니다
최적 부분구조 (Optimal Substructure) 전체 문제의 최적 해답이 부분 문제의 최적 해답으로 구성될 수 있는 성질 예: 서울→부산 최단경로가 서울→대전→부산이면, 서울→대전 구간도 반드시 최단경로
피보나치: fib(n) = fib(n-1) + fib(n-2) 전체 답이 부분 답의 조합으로 구성됩니다
중복 부분문제 + 최적 부분구조 = DP 적용 가능
비슷해 보이는 세 기법, 핵심 차이를 정리합니다
분할정복 (Divide & Conquer) • 부분 문제가 겹치지 않음 (예: Merge Sort) • 결과 저장 불필요 그리디 (Greedy) • 매 순간 최선을 선택 → 되돌아가지 않음 • 최적 부분구조는 필요하지만, 중복 부분문제는 아님 DP • 부분 문제가 겹침 → 결과를 저장·재사용 • 모든 경우를 고려하되 중복 계산을 제거
DP = 완전탐색의 효율화 중복만 제거하면 지수 시간이 다항 시간으로 변합니다
DP를 구현하는 방법은 두 가지가 있습니다
Top-Down (메모이제이션) • 재귀 + 결과 캐싱 • 필요한 부분문제만 계산 Bottom-Up (타뷸레이션) • 반복문 + dp 배열 • 작은 문제부터 순서대로 채움
다음 두 강의에서 각각을 자세히 배웁니다
DP가 적용 가능한 두 가지 조건은?
fib(n)의 순수 재귀 시간복잡도는 O(n)이다
DP의 세계에 입문!
핵심 용어
Dynamic Programming
하위 문제의 결과를 저장·재사용하여 효율적으로 푸는 기법
중복 부분문제
같은 하위 문제가 여러 번 반복 계산되는 구조
최적 부분구조
전체 최적해가 부분 문제의 최적해로 구성되는 성질
정리 노트
DP란? — 중복 부분문제와 최적 부분구조
핵심 개념
- Dynamic Programming
- 하위 문제 결과를 저장·재사용하여 중복 계산 제거
- 중복 부분문제
- 같은 하위 문제가 여러 번 반복 계산되는 구조
- 최적 부분구조
- 전체 최적해 = 부분 최적해의 조합
DP vs 유사 기법
- 분할정복
- 부분 문제가 겹치지 않음 (Merge Sort)
- 그리디
- 매 순간 최선 선택, 되돌아가지 않음
- DP
- 완전탐색 + 중복 제거 = 다항 시간
면접에서 '이 문제에 DP를 쓸 수 있는 이유'를 설명하라는 질문이 자주 나옵니다!
시각 자료
핵심 정리
- 1DP = 중복 부분문제 + 최적 부분구조
- 2순수 재귀 O(2^n) → DP 적용 시 O(n)
- 3Top-Down(메모이제이션)과 Bottom-Up(타뷸레이션) 두 방식
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작