[Algorithm] 범위에 따른 피보나치 수 구하는 방법

피보나치 수는 일반적으로 재귀적으로 구할 수 있지만 이 경우 함수 호출이 많아져서 많은 시간이 소요되게 됩니다. n 의 값에 따라서 이에 대해서 어떻게 접근해야할지가 다릅니다. 여러 문제를 해결하며 이를 알아보도록 하겠습니다.

 

BAEKJOON 247

피보나치 수 1

불러오는 중입니다...

n 번째 피보나치 수를 구하는 문제입니다. n 의 범위가 45 보다 작거나 같기 때문에 int 자료형으로 해결이 가능합니다.

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int fibo[46];
    
    fibo[0] = 0;
    fibo[1] = 1;
    
    for (int i=2;i<46;i++){
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    
    int N;
    cin >> N;
    
    cout << fibo[N] << "\n";
    
    return 0;
}

 

int 형은 아래와 같이 46 번째 까지 표현이 가능합니다.

0번째: 0
1번째: 1
2번째: 1
3번째: 2
4번째: 3
5번째: 5
6번째: 8
7번째: 13
8번째: 21
9번째: 34
10번째: 55
11번째: 89
12번째: 144
13번째: 233
14번째: 377
15번째: 610
16번째: 987
17번째: 1597
18번째: 2584
19번째: 4181
20번째: 6765
21번째: 10946
22번째: 17711
23번째: 28657
24번째: 46368
25번째: 75025
26번째: 121393
27번째: 196418
28번째: 317811
29번째: 514229
30번째: 832040
31번째: 1346269
32번째: 2178309
33번째: 3524578
34번째: 5702887
35번째: 9227465
36번째: 14930352
37번째: 24157817
38번째: 39088169
39번째: 63245986
40번째: 102334155
41번째: 165580141
42번째: 267914296
43번째: 433494437
44번째: 701408733
45번째: 1134903170
46번째: 1836311903
47번째: -1323752223

 

BAEKJOON 2748

피보나치 수 2

2748번: 피보나치 수 2

마찬가지로 n 번째 피보나치를 구하는 문제입니다. n 의 범위가 커졌기 때문에 int 대신 long long 자료형으로 해결이 가능합니다.

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    long long fibo[90];
    
    fibo[0] = 0;
    fibo[1] = 1;
    
    for (int i=2;i<91;i++){
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    
    int N;
    cin >> N;
    
    cout << fibo[N] << "\n";
    
    return 0;
}

 

BAEKJOON 2749

피보나치 수 3

2749번: 피보나치 수 3

n 의 범위가 1,000,000,000,000,000,000 로 급격하게 뛰었습니다. 하지만 1,000,000으로 나눈 나머지를 출력하기 때문에 해결할 수 있습니다. 이를 해결하기 위해서는 피사노 주기 를 알아야 합니다. 피사노 주기란 피보나치 수를 K 로 나눈 나머지는 주기를 갖는다는 것으로 예를 통해 살펴보겠습니다.

n       0   1   2   3   4   5   6   7   8   9  10  11  12  13  14 
fibo    0   1   1   2   3   5   8  13  21  34  55  89 144 233 377 
fibo%3  0   1   1   2   0   2   2   1   0   1   1   2   0   2   2 

K = 3 일 때, 0~7 번째 수와 8~14번째 수가 주기를 이루는 걸 확인할 수 있습니다. 즉 3 으로 나누었을 때, N 번째 피보나치 수를 구하기 위해서는 주기의 길이만큼만 계산을 해주면 됩니다. 위 경우에는 8번의 계산으로 해결할 수 있으므로 O(1) 입니다.

이 때 K 의 값이 10^k' 일 때 주기는 15*10^(k'-1) 임이 성립합니다. 따라서 주어진 문제에서 1,000,000(=10^6) 이므로 주기는 1,500,000(=15X10^5) 가 되고 N 의 범위인 10^18 까지 구하지 않고 1,500,000 까지만 구한 후 주기를 이용하여 답을 구해줄 수 있습니다.

#include <iostream>

using namespace std;

long long fibo[1500000];

int main(int argc, const char * argv[]) {
    
    fibo[0] = 0;
    fibo[1] = 1;
    
    for (int i=2;i<1500000;i++){
        fibo[i] = (fibo[i-1] + fibo[i-2]) % 1000000;
    }
    
    long long N;
    cin >> N;
    N = N % 1500000;
    
    cout << fibo[N] << "\n";
    
    return 0;
}

 

 

BAEKJOON 11444

피보나치 수 6

11444번: 피보나치 수 6

위에서 본 피보나치 수 3 과 마찬가지로 주기를 찾고 싶지만 1,000,000,007 로 나누기 때문에 주기를 찾는 공식이 있지 않고 직접 찾기에도 어렵습니다. 따라서 이 경우에는 아래와 같은 공식을 이용해 분할정복을 통해 구할 수 있습니다.

피보나치 수 공식

재귀적으로 구성하게 되면 함수 호출이 너무 많아지므로 map 을 이용해서 memorization 도 추가하였습니다.

#include <iostream>
#include <map>

using namespace std;

map<long long, long long> dic;

const long long DIV =1000000007LL;

long long fibo(long long n){
    if (n<0) cout << "n<0\n";
    if (n==0) return 0;
    else if (n==1) return 1;
    else if (dic[n] > 0) return dic[n];
    else if (n%2==0) {
        long long m = n/2;
        long long temp1 = fibo(m-1);
        long long temp2 = fibo(m);
        dic[n] = (2LL*temp1+temp2)*temp2;
        dic[n] %= DIV;
        return dic[n];
    }
    else {
        long long m = (n+1)/2;
        long long temp1 = fibo(m);
        long long temp2 = fibo(m-1);
        dic[n] = temp1*temp1 + temp2*temp2;
        dic[n] %= DIV;
        return dic[n];
    }
}

int main(int argc, const char * argv[]) {
    
    long long N;
    cin >> N;
    
    cout <<  fibo(N) << "\n";
    return 0;
}