다이나믹 프로그래밍 이해하기 - 피보나치

다이나믹 프로그래밍 - 백준

다이나믹을 푸는 방법은 다음과 같이 두 가지가 존재한다.

1. Top-down

2. Bottom-up

Top-down

먼저 문제를 작은 문제로 나누고, 작은 문제를 푼다. 작은 문제를 풀고나서 문제를 풀어버린다.

피보나치를 예로 들어보면

fibonacci(n) 이라는 문제를 풀어야 한다.

fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다.

fibonacci(n-1)과 fibonacci(n-2)를 호출해 작은 문제를 푼다.

fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 fibonacci(n)이라는 문제를 푼다.

대충 이런 식인것 같다.

Bottom-up

문제의 크기가 작은 문제 부터 차례대로 풀고 문제의 크기를 조금씩 크게 만들어서 문제를 점점 풀어나간다. 작은 문제를 풀면서 왔으므로 언젠가는 풀어야 하는 문제를 풀 수 있다.

int d[100];
 
 
 
int fibonacci(int n){
 
    d[0] = 1;
 
    d[1] = 1;
 
    for(int i=2; i<=n; i++){
 
        d[i] = d[i-1] +d[i-2];
 
    }
 
    return d[n]
 
}