[BaekJoon/백준] 2748번

피보나치 수열을 동적계획법으로 푸는 문제다.

 

 

동적계획법

 

- 동적 계획법은 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다

 

- 동적 계획법은, 쪼개지는 부분 문제가 중복될 때 메모이제이션을 사용하여 속도를 향상시키는 방법이다.

즉 하나의 문제가 부분 문제로 쪼개져서 푸는 문제에서, 같은 부분 문제들이 있다면 이들을 한 번만 실행하게끔만 구현해주는 것. (중복되는 문제에 대한 답을 여러 번 구할 필요가 없도록, 한 번 실행할 때 결과값을 캐시해놨다가 다음에 실행될 때는 캐시해놓은 값을 꺼내 쓰는것)

 

- 부분 문제로 쪼개서 원래의 답을 구한다는 점, 최적 부분 구조에서 사용된다는 점에서 분할정복과 비슷하나, 부분문제의 중복여부와 그로인한 메모이제이션 사용여부에 대한 차이가 있다.(즉, 동적계획법과 분할정복법의 차이점은 계산결과의 재활용 여부 )

 

 

피보나치 수열을 그냥 재귀함수로 구현하게 되면 아래와 같다.

//피보나치 수열을 재귀함수로 구현.
#include <iostream>
using namespace std;


long long fibo(int n) {
    if(n <= 1)
        return n;
    return fibo(n - 1) + fibo(n - 2);
}

int main() {
    int x;
    cin >> x;
    cout << fibo(x);
}

하지만 이렇게 되면, 숫자가 커질수록 속도가 당연히 기하급수적으로 느려지기 마련이다.

 

피보나치 수열 같은 알고리즘은, 1. 위에서 봤듯이 문제를 쪼개서 상위 문제의 답을 하위 부분문제의 답들로부터 구하는 구조이며 각 한 문제의 답이 일정하고(최적 부분 구조), 2. 이렇게 부분 문제가 쪼개질 때 중복되는 부분 문제들이 많이 존재한다(중복 하위 문제). 이런 경우 메모이제이션을 사용하는 동적계획법을 사용하여 성능을 높일 수 있다.

#include <iostream>
using namespace std;

long long memo[91]; // 메모이제이션.

long long fibo(int n) {
    if(n <= 1)
        return n;
    if(memo[n]>0)
        return memo[n];
    return memo[n] = fibo(n - 1) + fibo(n - 2);
}

int main() {
    int x;
    cin >> x;
    cout << fibo(x);
}

 

 

참고

velog.io/@polynomeer/동적-계획법Dynamic-Programming

galid1.tistory.com/507

chickenpaella.tistory.com/37

 

동적계획 vs 분할정복 비교 참고

euju-wouldyou.tistory.com/m/104?category=766590

freedeveloper.tistory.com/m/276