피보나치 수열

피보나치 수열이란? 수열의 각 항이 이전 두 항의 합으로 이루어진 수열이다. 첫 두 항은 1로 이루어져 있다.

예를 들어, 세 번째 항은 첫 번째 항 + 두 번째 항 = 1 + 1 = 2이다.

수열을 나열하면 다음과 같다.

1 1 2 3 5 8 13 21 34 55 ...

---

1. 단순 재귀를 이용한 구현

#include <iostream>

using namespace std;

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

// 재귀를 이용한 피보나치
int main(void){
    int n;
    cin >> n;
    cout << fibo(n) << "\n";
    return 0;
}

이 방식은 구현이 간단하지만, 매번 이전 값을 계산해야 하는 문제가 있어 n이 커질수록 기하급수적으로 시간이 증가한다.

 

2. dp를 적용한 재귀

#include <iostream>

using namespace std;

int fibo[100] = {0, };

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

// dp + 재귀를 이용한 피보나치
int main(void){
    int n;
    cin >> n;

    // fibo[] 초기화
    fibo[1] = fibo[2] = 1;

    cout << dpFibo(n) << "\n";
    return 0;
}

memoization 기법을 사용해 이전에 저장된 수열의 값을 다시 계산하지 않고 사용해 한 번씩만 계산하면 되므로 효율적이다.

 

3. 반복문 사용

#include <iostream>

using namespace std;

// 반복문을 이용한 피보나치
int main(void){
    int n;
    cin >> n;

    int prev = 1, cur = 1, next = 1;
    for(int i = 3; i <= n; i++){
        next = prev+cur;
        prev = cur;
        cur = next;
    }
    cout << next << "\n";

    return 0;
}

추가적인 메모리 사용 없이 구현할 수 있어 단순하다.