피보나치 수열

안녕하세요. 오늘은 피보나치 수열에 대해 다루어 보려고 합니다.

출처 : https://www.acmicpc.net/blog/view/28

피보나치 수열은 일반적으로 재귀형태로 구현을 많이 합니다.

하지만 이런 방식은 n이 커질수록 시간이 기하급수적으로 오래걸립니다.

그래서 좀 더 좋은 방식들에 대해 찾다보니 위의 링크에서 많은 정보를 얻었습니다.

위 내용에 추가적으로 살을 붙여서 정리해 보겠습니다.

Contents

재귀형식

재귀 + 저장(메모이제이션)을 이용한 방식

for-loop를 이용한 방식

피보나치 수의 나머지(피사노 주기)

피보나치 관계식의 행렬표현

+ 피보나치 수열의 합

재귀형식

---

재귀형식은 모두 다 아시다시피 아래와 같이 구현됩니다.

0, 1, 1, 2, 3, 5, 8, ... 이므로 n이 1보다 작으면 n을 아니면 점화식을 따라가면 됩니다.

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

이렇게 만들어진 형식은 아무래도 함수 호출당 함수 호출 수가 각 2배씩 늘어나므로 

만큼 시간복잡도가 걸리겠죠.

재귀 + 저장을 이용한 방식

---

그런데 재귀적인 호출에서 중복으로 호출이 되는 fibonacci 함수들 이 있다는 사실을 알고 계실 것입니다.

예를 들면 f(4)를 호출했을 때 f(3)과 f(2)가 호출되고, f(3)에서 f(2), f(1)이 호출이 되겠죠. 

여기까지만 봐도 f(2)가 두 번 등장함을 알 수 있습니다.

이렇게 중복된 함수의 호출인 경우 초기에 불러졌을 때 값을 저장해 놓고, 다음 호출에서는 값을 바로 꺼내 쓸 수 있도록 하면 어떨까요?

시간이 많이 줄어들겠죠! n인 경우 f(0)부터 f(n-1)까지 한번씩만 계산이 될것이므로 시간복잡도는

가 될 것입니다. (중복된 호출은 O(1)시간에 끝나기 때문입니다.)

여기서 중요한 것은 이 방식의 구현 시에는 저장공간의 크기를 항상 고려해 보아야 합니다.

(n의 범위가 적당하게 fixed되어 있다면 매우 좋은 방법일 수 있겠죠!)

int fibonacci(int n){
    if(n<=1) return n;
    else if(m[n]) return m[n];
    else return m[n] = fibonacci(n-1)+fibonacci(n-2);
}

For-loop을 이용한 방식

---

이 방식은 위의 재귀 + 저장 방식을 unroll한 방식이라고 생각하시면 됩니다.

피보나치 수열의 일반항을 그대로 0번째 부터 쭉 계산해 나가는 방식입니다.

이 방법 역시 시간복잡도는 

입니다.

int fibonacci(int n){
    int f[n+1] = {0, 1};
    for(int i = 2; i <= n; i++){
        f[i] = f[i-1]+f[i-2];
    }
    return f[n];
}

큰 피보나치 수의 나머지(피사노 주기)

---

문제 중에는 구하려는 수가 너무 커서 일정한 숫자 K의 나머지로 구하라는 문제가 있습니다.

피사노 주기

피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이 주기를 피사노 주기라 부릅니다.

특히 K가 10의  m승이고, m>2라면 주기는 15 x K/10이 됩니다.

수학적인 증명은 여기서는 다루지 않겠습니다. 우리는 이 사실을 잘 이용해 봅시다.

만약 K = 1,000,000 이라면 m = 6 이고 주기는 1,500,000가 됩니다. 

즉 1,500,000번째까지 나머지만 잘 구해놓으면 그 이상의 수는 주기성을 이용하여 금방 구할 수 있게 됩니다. 

와 진짜 이득!

물론 메모리 문제는 생각해야 될 문제이긴 한데..

#define P 1500000
#define K 1000000
int fibonacci(long long n){
    n %= P;
    int f[n+1] = {0, 1};
    for(int i = 2; i <= n; i++){
        f[i] = f[i-1] +f[i-2];
        f[i] %= K;
    }
    return f[n];
}

피보나치 관계식의 행렬표현

---

근데 피사노 주기를 이용하지 못하는 경우라면 어떡하죠..? 나머지 연산을 하라는데 10의 거듭제곱이 아니라면...?

그럴땐 관계식을 행렬로 표현하는 방식을 사용합니다.

우선 우리가 아는 관계식은 아래와 같습니다.

그럼 이를 행렬로 표현하면

가 될 것입니다. 그런데 우리는 이를 점화식으로 사용하기 위해 

로 만들 수 있습니다. 그러면 여러분은

를 얻게되고, 또 같은 식이지만

를 얻습니다. 식(1)과 (2)를 합쳐서 정리하면

가 되어 식이 깔끔하게 정리가 되죠!

그렇다면 행렬 {{1, 1},{1, 0}}의 n승의 성분을 통해 피보나치 수를 알아낼 수가 있습니다.

추가적으로 거듭제곱의 계산은 거듭제곱 수 n의 이진표현을 통해 빠르게 계산할 수 있는데 이 경우 시간복잡도는

가 됩니다.

#include<cstdio>
#include<vector>
#define mod 1000000007LL
using namespace std;
typedef vector<vector<long long> > matrix;
 
matrix operator*(matrix&a, 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;
    matrix ans = { {1, 0},{0, 1} };
    matrix x = { {1, 1},{1, 0} };
    scanf("%lld", &n);
    while (n) {
        if (n % 2 == 1) {
            ans = ans * x;
        }
        x = x*x;
        n /= 2;
    }
    printf("%lld\n", ans[0][1]);
    return 0;
}

피보나치 수열의 합

---

고등수학과정에도 나오지만 이 내용은 한번 더 알아두는 것이 좋습니다.

점화식이

이므로 

이 됩니다.

이 외에도 짝수항의 합은

이고 홀수항의 합은

이 됩니다.

피보나치 수열의 제곱수의 합은

가 됩니다.

이에 대한 수학적인 증명은 고등과정수준의 수식 전개이므로 직접해보실수 있을 것입니다!

---

질문이 있으시거나, 잘못된 내용을 발견하시면 댓글 남겨주시면 답변드리겠습니다.

감사합니다.