피보나치 수는 다음과 같이 정의되는 수열입니다.

• $F_0 = 0$
• $F_1 = 1$
• $F_n = F_{n-1} + F_{n-2}$

피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같습니다.

피보나치 수를 구하는 함수를 작성해보고 10870번 문제: 피보나치 수 5를 풀어보겠습니다.

#include <iostream>
using namespace std;
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << '\n';
    return 0;
}

이 방법은 재귀 호출을 이용한 방법입니다. 시간 복잡도는 대략 O(2^N) 정도가 나오게 됩니다. 정확하지는 않은 방법이지만, 한 함수는 두 개의 함수를 호출하게 됩니다. 따라서, 호출이 2배씩 늘어나게 되고, 총 단계의 최대값은 N번이기 때문에 O(2^N)으로 가늠해볼 수 있습니다.

여기에 메모이제이션을 추가해서 2747번 문제: 피보나치 수을 풀어보겠습니다.

#include <iostream>
using namespace std;
int memo[50];
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else if (memo[n] != 0) {
        return memo[n];
    } else {
        return memo[n] = fibonacci(n-1) + fibonacci(n-2);
    }
}
int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << '\n';
    return 0;
}

메모이제이션을 추가한 방법의 시간 복잡도는 O(N)입니다.

이번에는 이터레이티브한 방법으로 조금 터 큰 제한을 가지는 2748번 문제: 피보나치 수 2을 풀어보겠습니다. 90번째 피보나치 수는 long long범위이기 때문에, 다음과 같이 작성해볼 수 있습니다. 또, 이 방법 역시 시간 복잡도는 O(N)입니다.

#include <iostream>
using namespace std;
long long fibo[100] = {0,1};
int main() {
    int n;
    cin >> n;
    for (int i=2; i<=n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    cout << fibo[n] << '\n';
    return 0;
}

2749번 문제: 피보나치 수 3번은 지금까지 풀었던 세 문제와 똑같이 N번째 피보나치 수를 구하는 문제입니다. 그런데, N이 10¹⁸로 매우 큽니다. 다행히도 1,000,000로 나눈 나머지를 출력하는 문제네요.

피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period)라고 합니다.

피보나치 수를 3으로 나누었을 때, 주기의 길이는 8입니다.

주기의 길이가 P 이면, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같습니다.

M = 10^k 일 때, k > 2 라면, 주기는 항상 15 × 10^k-1 입니다. 이 사실을 모른다고 해도, 주기를 구하는 코드를 이용해서 문제를 풀 수 있습니다.

이 문제에서 M = 10⁶ 이기 때문에, 주기는 15 × 10⁵ = 1500000가 되겠네요.

#include <iostream>
using namespace std;
const int mod = 1000000;
const int p = mod/10*15;
int fibo[p] = {0,1};
int main() {
    long long n;
    cin >> n;
    for (int i=2; i<p; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
        fibo[i] %= mod;
    }
    cout << fibo[n%p] << '\n';
    return 0;
}

이제 11444번 문제: 피보나치 수 6를 풀어봅시다.

이 문제의 N 제한은 10¹⁸ 이지만, 1,000,000,007로 나눈 나머지를 구해야 합니다. 피사노 주기를 이용한 방법이 아니고, 행렬을 이용한 방법을 사용해야 합니다.

피보나치 수를 행렬로 나타내보면 아래와 같습니다.

$\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1&1 \\ 1&0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix}$

따라서, 식을 정리해 아래와 같이 나타낼 수 있습니다.

$\begin{pmatrix} F_{n+1}&F_n \\ F_n&F_{n-1} \end{pmatrix} = \begin{pmatrix} 1&1\\1&0 \end{pmatrix} ^ n$

어떤 수의 K제곱은 O(lgK)만에 구할 수 있습니다. (1629번 문제: 곱셈)

이 방법을 이용해 행렬 제곱을 빠르게 계산해서 문제를 풀 수 있습니다.

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<long long>> matrix;
const long long mod = 1000000007LL;
matrix operator * (const matrix &a, const matrix &b) {
    int n = a.size();
    matrix c(n, vector<long long>(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
            c[i][j] %= mod;
        }
    }
    return c;
}
int main() {
    long long n;

    cin >> n;

    if (n <= 1) {
        cout << n << '\n';
        return 0;
    }

    matrix ans = {{1, 0}, {0, 1}};
    matrix a = {{1, 1}, {1, 0}};

    while (n > 0) {
        if (n % 2 == 1) {
            ans = ans * a;
        }
        a = a * a;
        n /= 2;
    }

    cout << ans[0][1] << '\n';

    return 0;
}

다른 방법으로 11444번 문제: 피보나치 수 6를 풀어볼까요?

• $F_{2n-1} = F_n^2 + F_{n-1}^2$
• $F_{2n} = (F_{n-1} + F_{n+1})F_n = (2F_{n-1} + F_n)F_n$

입니다.

홀수 번째와 짝수 번째 피보나치수를 모두 더 작은 피보나치 수의 합 또는 곱을 이용해서 구할 수 있습니다.

따라서, 다음과 같은 메모이제이션 방법을 이용할 수도 있습니다.

#include <iostream>
#include <map>
using namespace std;
map<long long, long long> d;
const long long mod = 1000000007LL;
long long fibo(long long n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    } else if (d.count(n) > 0) {
        return d[n];
    } else {
        if (n % 2 == 1) {
            long long m = (n+1) / 2;
            long long t1 = fibo(m);
            long long t2 = fibo(m-1);
            d[n] = t1*t1 + t2*t2;
            d[n] %= mod;
            return d[n];
        } else {
            long long m = n/2;
            long long t1 = fibo(m-1);
            long long t2 = fibo(m);
            d[n] = (2LL*t1 + t2)*t2;
            d[n] %= mod;
            return d[n];
        }
    }
}
int main() {
    long long n;
    cin >> n;
    cout << fibo(n) << '\n';
    return 0;
}

피보나치 수는 다음과 같은 성질도 만족합니다.

• $\sum_{i=1}^{n}{F_i} = F_{n+2} - 1$
• $\sum_{i=1}^{n}{F_{2i}} = F_{2n+1} - 1$
• $\sum_{i=0}^{n}{F_{2i+1}} = F_{2n}$
• $\sum_{i=1}^{n}{F_i^2} = F_nF_{n+1}$
• $gcd(F_n,F_m) = F_{gcd(n,m)}$

피보나치 수와 관련된 다양한 문제를 풀어보세요!

• 10826번 문제: 피보나치 수 4
• 10870번 문제: 피보나치 수 5
• 1788번 문제: 피보나치 수의 확장
• 9471번 문제: 피사노 주기
• 2086번 문제: 피보나치 수의 합
• 11440번 문제: 피보나치 수의 제곱의 합
• 11442번 문제: 홀수번째 피보나치 수의 합
• 11443번 문제: 짝수번째 피보나치 수의 합
• 11524번 문제: Immortal Porpoises
• 11778번 문제: 피보나치 수와 최대공약수