10.1 피보나치 수열 [디딤돌 자료구조와 알고리즘 with C++]

10.1 피보나치 수열

피보나치 수열.cpp

피보나치 수열은 재귀적인 방법으로 해결하는 대표적인 알고리즘입니다. 하지만 피보나치 수열에서는 내부적으로 두 번의 재귀를 수행하여 재귀 호출 횟수는 2의 n승으로 수행 비용이 많이 들어갑니다.

 

만약 한 번 구한 항의 값을 기억해 두었다가 다시 호출할 때 이를 이용하면 비용은 줄어들어요. 이와 같이 경험한 정보를 이용하여 문제를 해결하는 것을 동적 프로그래밍 기법이라 말합니다. 여기에서는 피보나치 수열을 재귀적인 방법과 동적 프로그래밍 방법으로 해결하는 것을 비교해 볼게요.

 

다음은 피보나치 수열을 재귀적인 방법으로 구현한 코드입니다.

unsigned long long Fibonacci(unsigned int n)

{

    long long result = 1;

    if(n<=0)

    {

        return 0;

    }

    if((n==1)||(n==2))

    {

        return 1;

    }

    else

    {

        return Fibonacci(n-1)+Fibonacci(n-2);

    }

}

 

다음은 동적 프로그래밍으로 구현한 코드입니다. 수행한 경험이 있는 값들을 보관하는 테이블이 필요합니다. 테이블의 0항은 0으로 1과 2항은 1로 설정하고 나머지는 0으로 초기화합니다. 테이블에 값이 0이면 계산하고 0이 아니면 테이블의 값을 반환합니다.

unsigned long long value_table[100]={0,1,1};

unsigned long long Dynamic_Fibonacci(unsigned int n)

{   

    if(n<=0)

    {

        return 0;

    }

    if(value_table[n]==0)

    {

        value_table[n] = Dynamic_Fibonacci(n-1)+Dynamic_Fibonacci(n-2);

    }

    return value_table[n];

}

 

다음은 둘의 수행 시간을 비교하기 위한 테스트 코드예요.

int main(void)

{

    int i = 0;

    long long value=0,value2=0;

    clock_t st,et;

21번재 항부터 35번째 항까지 수행하는 시간을 측정하여 출력하기로 합시다.

    for( i = 21; i<=35;i++)

    {  

        cout<<"==== "<<i<<" ===="<<endl;

        st = clock();

        value = Fibonacci(i);

        et = clock();

        cout<<"재귀 호출을 이용 Fibonacci("<<i<<")="<<value<<", "<<et-st<<"clocks"<<endl;       

 

        st = clock();

        value2 = Dynamic_Fibonacci(i);

        et = clock();

        cout<<"동적 프로그래밍 Fibonacci("<<i<<")="<<value<<", "<<et-st<<"clocks"<<endl;       

    }   

    return 0;

}

 

▷ 실행 결과

==== 21 ====

재귀 호출을 이용 Fibonacci(21)=10946, 0clocks

동적 프로그래밍 Fibonacci(21)=10946, 0clocks

==== 22 ====

재귀 호출을 이용 Fibonacci(22)=17711, 3clocks

동적 프로그래밍 Fibonacci(22)=17711, 0clocks

==== 23 ====

재귀 호출을 이용 Fibonacci(23)=28657, 4clocks

동적 프로그래밍 Fibonacci(23)=28657, 0clocks

==== 24 ====

재귀 호출을 이용 Fibonacci(24)=46368, 5clocks

동적 프로그래밍 Fibonacci(24)=46368, 0clocks

==== 25 ====

재귀 호출을 이용 Fibonacci(25)=75025, 9clocks

동적 프로그래밍 Fibonacci(25)=75025, 0clocks

==== 26 ====

재귀 호출을 이용 Fibonacci(26)=121393, 13clocks

동적 프로그래밍 Fibonacci(26)=121393, 0clocks

==== 27 ====

재귀 호출을 이용 Fibonacci(27)=196418, 20clocks

동적 프로그래밍 Fibonacci(27)=196418, 0clocks

==== 28 ====

재귀 호출을 이용 Fibonacci(28)=317811, 32clocks

동적 프로그래밍 Fibonacci(28)=317811, 0clocks

==== 29 ====

재귀 호출을 이용 Fibonacci(29)=514229, 55clocks

동적 프로그래밍 Fibonacci(29)=514229, 0clocks

==== 30 ====

재귀 호출을 이용 Fibonacci(30)=832040, 87clocks

동적 프로그래밍 Fibonacci(30)=832040, 0clocks

==== 31 ====

재귀 호출을 이용 Fibonacci(31)=1346269, 138clocks

동적 프로그래밍 Fibonacci(31)=1346269, 0clocks

==== 32 ====

재귀 호출을 이용 Fibonacci(32)=2178309, 230clocks

동적 프로그래밍 Fibonacci(32)=2178309, 0clocks

==== 33 ====

재귀 호출을 이용 Fibonacci(33)=3524578, 367clocks

동적 프로그래밍 Fibonacci(33)=3524578, 0clocks

==== 34 ====

재귀 호출을 이용 Fibonacci(34)=5702887, 600clocks

동적 프로그래밍 Fibonacci(34)=5702887, 0clocks

==== 35 ====

재귀 호출을 이용 Fibonacci(35)=9227465, 974clocks

동적 프로그래밍 Fibonacci(35)=9227465, 0clocks

 

수행 결과를 보면 재귀 호출을 이용하여 구현한 피보나치 수열은 n이 커질 수록 소요하는 시간은 기하급수적으로 늘어나는 것을 볼 수 있습니다. 하지만 동적 프로그래밍은 경험 정보를 이용하기 때문에 매우 빠르게 수행함을 알 수 있습니다.