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

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

  • $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 \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로 나눈 나머지를 구해야 합니다. 피사노 주기를 이용한 방법이 아니고, 행렬을 이용한 방법을 사용해야 합니다.

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

$\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)}$

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

댓글 (6개) 댓글 쓰기


hanjungv 1년 전

잘보고갑니당~


namnamseo 1년 전

일반항을 이용해서 특정 문제를 풀 수 있으니 그 점도 나와있으면 좋을 것 같아요!


baekjoon 1년 전

어떤 문제를 풀 수 있나요??


nhs0912 6달 전

피보나치를 행렬을 이용한 방법이 이해가 안되네요..ㅠㅠ 왜 피보나치 수를 행렬로 나타나면 저렇게 되는지 모르겠는데 알려주실 수 있나요???


ingyo 1달 전

피보나치 수 6의 경우 피사노 주기를 이용한 방법은 불가한 이유가 무엇인지 궁금합니다~


namnamseo 1달 전

피보나치 수 3의 문제를 볼게요. 1,000,000의 피사노 주기가 1,500,000이기 때문에,

(n번째 피보나치 수)를 (1,000,000)으로 나눈 나머지 = ((n % 1,500,000)번째 피보나치 수)를 (1,000,000)으로 나눈 나머지

임을 알 수 있습니다. 피사노 주기의 정의 때문에요. 그러면 우리가 구해야 하는 피보나치 수는, n의 최대 제한인 1,000,000,000,000,000,000번째까지가 아니라, 1,500,000번째까지로 확 줄었습니다. 크기가 1,500,000인 int 배열을 그냥 순서대로 채워나가면 1,500,000번째 피보나치 수까지는 쉽고 빠르게 구할 수 있습니다. 1초도 안 걸려요.

그런데... 1,000,000,007에 대한 피사노 주기가 몇인지는 저는 잘 모르겠지만, 그 주기가 T라고 하면, T번째의 피보나치 수까지는 일단 구할 수 있어야 합니다. (이해가 안 된다면 위의 1,000,000의 예시를 다시 한 번 읽어주세요.) 그런데 1,000,000,007은 (정수론을 도입해서 풀어내면) 그 T가 2,000,000,016입니다. 이 크기의 배열을 선언할 수도 없고, 저 횟수만큼 반복문을 돌리면 절대로 시간 안에 돌아갈 수가 없네요. 때문에 피사노 주기를 이용한 방법은 불가능합니다.

도움이 되셨나요?