피보나치 수를 구하는 여러가지 방법

이미지가 깨져서 출처에 가서 읽는 것을 추천

출처: https://www.acmicpc.net/blog/view/28?utm_content=bufferbde02&utm_medium=social&utm_source=facebook.com&utm_campaign=buffer

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

• $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(2N) 정도가 나오게 됩니다. 정확하지는 않은 방법이지만, 한 함수는 두 개의 함수를 호출하게 됩니다. 따라서, 호출이 2배씩 늘어나게 되고, 총 단계의 최대값은 N번이기 때문에 O(2N)으로 가늠해볼 수 있습니다.

여기에 메모이제이션을 추가해서 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이 1018로 매우 큽니다. 다행히도 1,000,000로 나눈 나머지를 출력하는 문제네요.

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

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

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$F_n$	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610
$F_n\mathrm{mod}3$	0	1	1	2	0	2	2	1	0	1	1	2	0	2	2	1

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

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

이 문제에서 M = 106 이기 때문에, 주기는 15 × 105 = 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 제한은 1018 이지만, 1,000,000,007로 나눈 나머지를 구해야 합니다. 피사노 주기를 이용한 방법이 아니고, 행렬을 이용한 방법을 사용해야 합니다.

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

$\left(\begin{array}{c}{F}_{n+2}\\ F_{n+1}\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right)$

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

$\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^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_n{F}_{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번 문제: 피보나치 수와 최대공약수