피보나치 수열의 다양한 구현방법

피보나치 수열이란, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다.

즉 f(t) = f(t-1) + f(t-2)를 만족시키며,

실제 수는 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 로 나아간다.

 

피보나치 수열은 재귀함수의 활용이나 동적 계획법을 연습하는 데 흔히 쓰인다.

다양한 풀이 방법을 통해 피보나치 수열을 구현하는 법을 알아보자

 

일반적인 재귀호출을 통한 구현

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

시간 복잡도는 함수가 한 번 호출되면 다시 두 번 호출되기 때문에 지수적으로 증가해 O(2^n)이 된다.

 

 

반복문을 이용한 구현

만약 10번째 피보나치 수를 찾고 싶다면 0번째(0), 첫 번째(1) 피보나치 수부터 계속 반복적으로 더해서  최종적으로 10번째 수까지의 합에 도달할 수 있다.

int FiboLoop(int n){
    int before=0, cur=1, i, temp;
 
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else{
        for (i = 1; i < n; i++){
            temp = cur;
            cur = before + cur;
            before = temp;
        }
        return cur;
    }
}

 

동적 계획법을 사용한 풀이

실제로는 반복문이나 재귀를 사용해서 피보나치 수열을 구하면 긍정적인 시간 내에서 결과가 나오지는 않을 것이다. 이러한 이유는 피보나치 수열의 재귀적 특성에 있다. 

그림에서 7번째 값을 구하기 위해 fib(3)은 5번이나 중복되어 등장한다. 이는 n 이 커질수록 기하급수적으로 커진다.

 

결국 문제는 피보나치 수열을 구하기 위한 부분문제들이 fib(0), fib(1) 를 만나기 전까지 계속 쪼개지며 너무나 많이 등장한다는 것이다. 정확히는 부분문제가 많은 것보다도 부분문제가 중복(overlapping subproblems)된다는 것이 문제다.

 

그래서 사람들은 부분문제가 너무 많이 중복되는 것이 문제라면, 각 부분문제를 해결할 때마다 그것을 저장하고 필요할 때마다 가져다 쓰면 된다고 생각하게 되었다. 그래서 나온 풀이법이 동적 계획법을 이용해 피보나치 수열을 구하는 방식이다

int Dynamic_FIB(int n)
{
	int *arr = new int[n + 1];

	arr[0] = 0;
	arr[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	return arr[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.html

피보나치 수열 알고리즘을 해결하는 5가지 방법

https://xtar.tistory.com/43