큰 문제를 작은 문제로 나누어 푸는 알고리즘.
줄여서 DP, 한글로 동적계획법 이라 불린다.
1. 문제 조건
이 방법으로 해결하기 위한 문제의 조건은 아래와 같다.
-
Overlapping Subproblem
: 겹치는 작은 문제
예) Fn = Fn-1 + Fn-2 -
Optimal Substructure
: 최적 부분 구조, 문제의 정답을 작은 문제의 정답에서 구할 수 있어야한다.
예) F4 = F3 + F2, F5 = F4 + F3 에서 F4, F5를 구할때 F3의 값은 같아야한다.
2. DP 특징
- memorization을 함
분할정복(EX.정렬)과 유사하지만 분할정복은 memorization 하지않음.
3. 구현 방식
- Top-down
: 재귀 사용
int fibonacci(int n){
if (n <= 1) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
]- Bottom-up
: 반복문 사용
int fibonacci(int n){
d[0] = 0;
d[1] = 1;
for (int i=2; i<=n; i++){
d[i] = d[i-1] + d[i-2];
}
return d[n];
]- 파이썬의 경우, Top-Down 사용하면 시간초과. 왜냐면 top-down은 메모리초과, 시간이 오래걸리기 때문이다.
4. 구현 전략
(1) 점화식의 정의를 세우기
D[n] = n번째 피보타치 수
(2) 문제를 작게 만들 수 있는 방법을 찾기
n번째 피보나치 수는 n-1번째와 n-2번째를 더해서 만든다.
(3) 점화식 세우기
D[n] + D[n-1] + D[n-2]
