알고리즘 - 피보나치 수열

 

피보나치수열은 

0, 1, 1, 2, 3, 5 ,8...

이런 순서로 앞의 수와 뒤의 수가 서로 더한 값을 수열 형태로 나타낸 것. (Fn = Fn-1 + fn-2)

 

 

 

피보나치수열을 구현하는 방법은 대표적으로 재귀 함수와 반복문을 이용하는 방법들이 있다. 

 

우선 재귀함수로 피보나치수열을 구현하는 방법

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

이렇게 구현할 수 있다. 

 

하지만 재귀함수로 구현하면 반복문 방식보다 오버헤드가 심하기 때문에 메모리 낭비가 생기게 된다. 

 

 

 

 

 

위의 단점은 극복한 방법이 바로 아래의 반복문을 이용한 방법이다. 

def solution(n):
    fibo = [0, 1, 1]
    for i in range(3, n + 1):
        fibo.append( ( fibo[i-1] + fibo[i-2] ) )
    
    return fibo[-1]

 

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    
    vector<int> fibo = {0, 1, 1};
    
    for(int i=3; i<=n; i++ )    
        fibo.push_back( ( fibo[i-1] + fibo[i-2] ) );
    
    
    return fibo.back();
}

 

재귀 함수 방식과 반복문 방식을 서로 비교를 해보았는데 

재귀 함수가 피보나치수열을 10번째 자리까지 구하는 메모리 용량이 반복문은 무려 100번째 자리까지 구하는 메모리의 용량과 똑같이 나왔다.