[코딩테스트] 피보나치 수

1. 재귀함수

int Fibonachi(int n)
{
    if(n <= 1)
        return n;
    else
        return Fibonachi(n-1) + Fibonachi(n-2);
}

int main()
{
    int n = 10;
    cout << Fibonachi(n);
}

재귀함수를 이용하여 피보나치를 구현하는 경우, 시간복잡도가 O(2^n)으로, n이 커질수록 시간복잡도가 기하급수적으로 증가한다.

---

2. vector

int main()
{
    int answer = 0;
    
    vector<int> fibonachi;
    
    fibonachi.push_back(0);
    fibonachi.push_back(1);
    
    for(int i=2; i<=n; ++i)
    {
        fibonachi.push_back((fibonachi[i-2] + fibonachi[i-1]));
    }
    
    answer = fibonachi[n];
}

벡터를 이용하여 피보나치를 구현하는 경우, 각 피보나치 수를 한 번만 계산하므로 시간복잡도가 O(n)에 해당한다.