피보나치 수

수학에서 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

 

재귀함수를 통해 푸는 방법은 가장 기본적이지만 수가 커질수록 함수 오버플로우가 발생한다. 즉, 시간초과.

#include <string>
#include <vector>
using namespace std;

int fibonacci(int n)
{
    if(n == 1 || n == 2)
        return 1;
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

시간초과를 해결하는 방법은 Bottom to Top 의 방향으로 쉽게 구현할 수 있다.

n번째 피보나치 수를 구하기 위해 이전 값들은 참조만 하는 형식으로 해야한다.

#include <string>
#include <vector>

using namespace std;

int fibonacci(int n)
{
    vector<int> fibo;	// 0, 1을 넣고 시작
    fibo.emplace_back(0);
    fibo.emplace_back(1);
    
    for(int i = 2; i<= n; i++)
    {
    	fibo[2] = fibo[0] + fibo[1];    // 항상 (n-1) + (n-2)의 값이 저장됨
        fibo[0] = fibo[1];
        fibo[1] = fibo[2];
    }
    
    return fibo[2];
}