[C/C++] 피보나치 수열 알고리즘(피사노 주기)

피보나치 수열(Fibonacci Sequence)은 단순한 단조 증가(monotonically increasing) 수열로, 0번째 항은 0, 1번째 항은 , 그 외 항은 전 항과 전전 항의 합으로 표현됩니다.

피보나치 수열은 재귀 함수의 활용이나 동적 계획법을 연습하는 데 흔히 사용됩니다. 피보나치 수열을 해결하는 6가지 방법에 대해 알아보겠습니다.

 

1. 재귀적 방법

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

위 알고리즘의 시간 복잡도는 O(2^n) 입니다. 함수가 한 번 호출되면 다시 두 번 호출되기 때문에 시간 복잡도가 지수적으로 증가하게 됩니다.

 

2. 반복문을 활용한 방법

int fibonacci(int n) {
	if(n<2) return n;
    else {
    	int x=0;
        int y=1;
        
        for(int i=0;i<n;i++) {
        	y=x+y;
            x=y;
        }
        return y;
    }
}

위 알고리즘의 시간 복잡도는 O(n) 입니다. n이 2 미만이면 n을 그대로 반환하고, 2 이상일 때는 n-1번 만큼 반복문을 시행합니다. 이는 앞선 재귀에 비해 효율적인 방법입니다.

 

3. 동적 계획법(Dynamic Programming)을 활용한 방법

7번째 피보나치 수를 구할 때의 과정을 표현하고 있습니다. 7번째 값을 구하기 위해서는 5, 6번째 값을 구해야 합니다. 이와 같이 '부분 문제 해결'을 통해 피보나치 수를 구하고 있습니다. 부분 문제 해결 방식으로는 재귀적 풀이(recursive)와 반복문을 사용하는 반복적 풀이(iterative)가 있습니다.

 

3-1. 반복적 동적 계획법 풀이

long long fibonacci(int n) {
	long long fibo[n+1];

	fibo[0]=0;
	fibo[1]=1;

	if(n<2) return n;
	else {
        for(int i=2;i<=n;i++) {
            fibo[i]=fibo[i-1]+fibo[i-2];
    	}
        return fibo[n];
    }
}

 

3-2. 재귀적 동적 계획법 풀이

long long fibonacci(int n) {
	long long fibo[n+1];
    
	for(int i=0;i<=n;i++) fibo[i]=-1;
    
    if(fibo[n]!=-1) return fibo[n];
    fibo[n]=fibonacci(n-1)+fibonacci(n-2);
    
    return fibo[n];
}

 

4. 행렬 곱셈을 활용한 방법

피보나치 수들을 행렬화하면 위와 같은 식이 됩니다.

 

5. 일반항 사용

위 식은 n번째 피보나치 수를 구하는 일반항입니다. 이 식을 구현하게 되면 시간 복잡도는 O(logn)이 됩니다.

 

6. 피사노 주기

피보나치 수를 어떤 수 M으로 나눌 때 그 나머지는 항상 주기를 가지게 되는데, 이를 피사노 주기라고 합니다.

P(주기의 길이)=15*10^(k-1)

M(나누는 수)=10^k (k>2)

 

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

n번째 피보나치 수를 M으로 나눈 나머지를 구하고자 하는데 n이 매우 큰 값일 경우, 피사노 주기를 사용해야 합니다.

 

출처: https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95, https://comyoung.tistory.com/236