백준-피보나치 수 5(10870번)

재귀함수 문제중에 흔한 피보나치 문제입니다. 

 

 

피보나치란?

 

 

백준의 해당 문제 같은 경우에는 0번째 항부터 시작하는 피보나치를 제시해줬습니다. 

 

코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int Fibo(int n)
{
    if(n==0)
        return 0;

    else if(n==1)
        return 1;

    else
        return Fibo(n-1)+Fibo(n-2);
}

int main()
{
    int input;
    cin>>input;

    cout<<Fibo(input);
}

위 코드로도 정답처리는 되지만 속도를 더 향상시킬수 있는 여지가 있습니다. 

 

Fibo함수의 마지막 else문을 보시면 

return Fibo(n-1)+Fibo(n-2);

이 부분에서 최적화할 수 있습니다. 

 

---

 

 

 

출처: 나무위키 동적계획법

위와 같이 fib(5)를 계산하려면 총 15번의 함수 호출이 발생합니다. 

 

그림을 보면 fib()가 중복되는 것들이 매우 많은것을 알 수 있습니다. 

 

이렇게 하면 숫자가 커지면 커질수록 트리의 크기는 지수 스케일로 커지게 될 것이고

당연하게도 시간 복잡도와 공간 복잡도도 지수 스케일로 증가합니다.(Exponential Explosion)

 

이러한 문제를 해결하는 방법을 동적 계획법(dynamic programming, DP)라고 합니다.

동적 계획법은 했던 계산을 또 하고 또 하는 종류의 문제인 최적 부분 구조(Optimal Substructure)문제에서 효과적입니다.

---

동적계획법의 대표적인 방식은 Top-down과 Bottom-up으로 나뉩니다.

 

먼저,Top-down은 위에서 아래로, 즉 큰 문제부터 시작해서 계속 작은 문제로 분할해 가면서 푸는 방식입니다.

 

그 방법은, 한번 계산한것은 따로 저장을 해둬서 다음에 해당 값을 요구하는 함수가 호출되면 다시 계산하는 것이 아닌,

저장된 값을 바로 불러와서 사용하는 것입니다. 계산값을 저장해 놓는걸 메모이제이션(Memoization)이라고 합니다.

#include<iostream>
using namespace std;

int memo[100]{}; //메모이제이션 공간. 전역 변수이므로 0으로 초기화

int fibonacci(unsigned int n)
{
  if (n<=1) //0번째, 1번째 피보나치 수
    return n;
  if (memo[n]!=0) //메모가 있는지 확인(0으로 초기화되었으므로 0이 아니라면 메모가 쓰인 것임)
    return memo[n]; //메모 리턴
  memo[n]=fibonacci(n-1) + fibonacci(n-2); //작은 문제로 분할
  return memo[n];
}

전역으로 배열을 생성해서 그곳에 계산한 값을 저장해 놓고 이미 계산한 값이라면 바로 불러오는 방식을 사용합니다.

그렇지만 n이 커지면 최대 재귀 깊이 초과 문제가 발생하기 때문에 이럴땐 bottom-up방식으로 해결이 가능합니다.

(재귀 호출로 인한 스택 오버플로우)

 

 

 

 

Bottom-up은 아래에서 위로, 즉 작은 문제부터 시작해서 점점 쌓아서 큰 문제를 푸는 방식입니다.

첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 구하면 세번째 피보나치 수를 구할수 있고, 

두 번째 피보나치수와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있듯,

이 방식을 반복하여 n번째 피보나치 수를 구합니다.

#include<iostream>
using namespace std;

int f_data[N] = {1, 1}; // N은 정의하기 나름
int last_pos = 1; // 마지막으로 계산한 지점. 이 코드에선 이미 f_data[1]까지 정의되어있기 때문에 1로 초기화한다.

int f(int n) //피보나치 수열의 제 n항을 구한다. 배열의 관점에서는 n-1번째 요소를 구하는 것.
{
    int i;
    if(f_data[n-1] == 0)  // 아직 구한 적이 없으면 구한다
    {
        for(i=last_pos+1; i<n; ++i)
        {
            f_data[i] = f_data[i-1] + f_data[i-2];
        }
        last_pos = n-1;
    }
    return f_data[n-1];
}

이렇듯 Bottom-up은 Top-down에 비하여 재귀 호출을 하지 않기때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있습니다.

(+ n이 커질때 생기는 최대 재귀 깊이 초과 문제 회피가능)