다이나믹 프로그래밍
│
├─ 패러다임
│ │
│ 분할정복: 중복된 하위 분제들 and 최적 부분 구조
│
└─ 방법론
├ 하향식 접근법: 메모이제이션
└ 상향식 접근법: 타뷸레이션
동적계획법이라고도 한다
동적?
최적 부분 구조(Optimal Substructure) 갖는 문제 풀이 가능
최적 부분 구조(Optimal Substructure)? 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제| 동적계획법 | 그리디 |
|---|---|
| 가능한 모든 방법 고려 | 그 순간에 최적인 방법 고려 |
| 항상 최적 | 항성 최적 아니다 |
| 동적계획법 | 분할정복 |
|---|---|
| 부분 문제가 중복되고 공유된다 | 서로 겹치지 않는(disjoint) 부분 문제로 분할 |
| 알고리즘 | 풇이 가능한 문제들의 특징 | 풀이 가능한 문제 및 알고리즘 |
|---|---|---|
| 동적계획법 | 최적 부분 구조, 중복된 하위 문제들 |
0-1(분할 불가) 배낭 문제, 피보나치 수열, 다익스트라 알고리즘 |
| 그리디 | 최적 부분 구조, 탐욕 선택 속성 |
분할 가능 배낭 문제, 다익스트라 알고리즘 |
| 분할정복 | 최적 부분 구조 |
병합 정렬, 퀵 정렬 |
최적 부분 구조 ┌──────300 km────┐ ┌──120 km───┐
서울─────200 km────대구──80 km──부산
└──────250 km────┘ └──100 km───┘
최적 부분 구조라 한다서울 - 부산 새로운 고속도로가 새통되면 굳이 대구를 거칠 필요가 없으며, 그때는 더이상 최적 부분 구조가 아니다.중복된 하위 문제(Overlapping Subproblem)f(5) = f(4) + f(3) = 5
│ │
│ f(3) = f(2) + f(1) = 2
│ │ │
│ │ f(1) = 1
│ f(2) = 1
│
f(4) = f(3) + f(2) = 3
│ │
│ │
│ f(2) = 1
│
f(3) = f(2) + f(1) = 2
│ │
│ f(1) = 1
│
f(2) = 1
f(5)를 계산하기 위해,
f(3)은 두번 중복f(2)는 세 번 중복f(1)은 두 번 중복타뷸레이션(Tabulation)이라 부른다
Bottom-up
def fib_bottom_up(n):
dp = []
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i -2]
return dp[n]
function fib_tabulation(num) {
const table = {};
table[0] = 0;
table[1] = 1;
for (let i = 2; i < num + 1; i++) {
table[i] = table[i - 1] + table[i - 2];
}
return table[num];
}
메모이제이션(Memoization)이라 부른다
referential transparent function)에만 적용 가능Top-Down
def fib_top_down(n, dp):
if n <= 1:
return n
if n in dp:
return dp[n]
dp[n] = fib_top_down(n - 1, dp) + fib_top_down(n - 2, dp)
return dp[n]
// call stack이 지수적으로 증가한다
function fib_memoization(num, memo) {
if (num <= 1) return num;
if (memo.hasOwnProperty(num)) return memo[num];
memo[num] = fib_memoization(num - 1, memo) + fib_memoization(num - 2, memo);
return memo[num];
}