0verview 다이나믹 프로그래밍
다이나믹 프로그래밍
개요
다이나믹 프로그래밍
│
├─ 패러다임
│ │
│ 분할정복: 중복된 하위 분제들 and 최적 부분 구조
│
└─ 방법론
├ 하향식 접근법: 메모이제이션
└ 상향식 접근법: 타뷸레이션
동적계획법이라고도 한다동적?- 시가변적(time-varing)
- 다단계적(multistage)
- 개념
- 문제를 각각의 작은 문제로 나누어 해결
- 해결한 결과를 저장
- 저장된 결과를 나중에 큰 문제의 결과와 합하여 풀이
최적 부분 구조(Optimal Substructure)갖는 문제 풀이 가능최적 부분 구조(Optimal Substructure)? 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제
다이나믹 프로그래밍 vs 그리디 알고리즘
| 동적계획법 | 그리디 |
|---|---|
| 가능한 모든 방법 고려 | 그 순간에 최적인 방법 고려 |
| 항상 최적 | 항성 최적 아니다 |
다이나믹 프로그래밍 vs 분할 정복
- 둘 다 큰 문제를 작은 문제로 분할한다는 점에서는 같지만, 분할되는 부문 문제에서 차이가 있다
| 동적계획법 | 분할정복 |
|---|---|
| 부분 문제가 중복되고 공유된다 | 서로 겹치지 않는(disjoint) 부분 문제로 분할 |
알고리즘과 풀이 가능한 문제들의 특징
| 알고리즘 | 풇이 가능한 문제들의 특징 | 풀이 가능한 문제 및 알고리즘 |
|---|---|---|
| 동적계획법 | 최적 부분 구조, 중복된 하위 문제들 |
0-1(분할 불가) 배낭 문제, 피보나치 수열, 다익스트라 알고리즘 |
| 그리디 | 최적 부분 구조, 탐욕 선택 속성 |
분할 가능 배낭 문제, 다익스트라 알고리즘 |
| 분할정복 | 최적 부분 구조 |
병합 정렬, 퀵 정렬 |
다이나믹 프로그래밍 패러다임
최적 부분 구조
┌──────300 km────┐ ┌──120 km───┐
서울─────200 km────대구──80 km──부산
└──────250 km────┘ └──100 km───┘
- 최단 경로는? 200 + 80 = 280
- 서울에서 대구까지 가는 최단 경로 문제
- 대구에서 부산까지 가는 최단 경로 문제
- 즉, 문제의 최적 해결 방법 = 부분 문제에 대한 최적 해결 방법으로 구성
- 이러한 구조를
최적 부분 구조라 한다
- 이러한 구조를
- 반면
서울 - 부산새로운 고속도로가 새통되면 굳이 대구를 거칠 필요가 없으며, 그때는 더이상 최적 부분 구조가 아니다.
중복된 하위 문제(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)이라 부른다- 데이터를 테이블 형태로 만들면서(Tabulate) 문제를 풀이 의미
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];
}
다이나믹 프로그래밍 알고리즘 설계
- 최적해의 구조의 특징을 찾는다
- 최적해의 값을 재귀적으로 정의한다
- 최적해의 값을 일반적으로 상향식 방법으로 계산
- 계산된 정보들로부터 최적해를 구성