Dynamic Programming

다이나믹 프로그래밍은 하나의 문제는 단 한 번만 풀도록 하여 계산 수를 줄이는 효율적인 알고리즘이다.

분할 정복과 비교

다이나믹 프로그래밍을 얼핏 봤을 때는 분할 정복과 다를게 없어보인다. 하지만 분할 정복의 계산을 여러번 해야 하는 점을 본다면 이는 다이나믹 프로그래밍과 다른 것을 알 수 있다. 피보나치 수열은 분할 정복으로 해결할 때 효율성이 크게 떨어진다.

만약 피보나치 수열의 arr[11]을 구하는 문제가 있다면, arr[11]을 구하기 위해 arr[10]과 arr[9]를 알아야 하고, arr[10]을 알기 위해 arr[9]와 arr[8]을 알아야한다. 이 부분에서 매우 많은 연산이 발생하는 것을 알 수 있다.

사용 조건

• 큰 문제를 작은 문제로 나눌 수 있어야 한다.
• 작은 문제에서 도출된 결과는 큰 문제에서도 동일해야 한다.

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 해결하여 처리한 뒤 이를 모아서 답을 구하는 방식이다. 이 과정에서 반복 연산이 아닌 Memoization을 사용하기 때문에 문제를 효율적으로 해결할 수 있다. 분할 정복과 다르게 계산한 결과를 배열에 저장하여 반복 연산의 수를 줄인다.

분할 정복과 마찬가지로 피보나치 수열의 arr[11]을 구하는 문제가 있다면, arr[11]을 구하기 전까지의 결과들을 memoization 배열에 저장하여 한번 구한 결과는 다시 계산하지 않게 된다.

Code

#include <iostream>
using namespace std;

int asw[100];

int fibo(int x){
	if(x==1) return 1;
    if(x==2) return 1;
    if(asw[x]!=0) return asw[x];
    return fibo(x-2)+fibo(x-1);
}
int main(){
	cout<<fibo(11)<<endl;
    return 0;
}