Fibonacci & Dynamic Programming( 피보나치수열 & 동적계획법)

피보나치수열 과 동적계획법

원리    : n번째 수 = n-1번째 수 + n-2번째 수

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

< 피보나치수열 알고리즘 >

#include<stdio.h>

int fibonacci ( n ) { 

if ( n == 0 ) { 

return 0 ;

}else if ( n == 1 ){

return 1;

}else {

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

}

} 

int main( void ) {

int n = 0 ;

int result = 0;

scanf( "%d" , &n );

result = fibonacci ( n ) ;

printf("%d\n" , result );

return 0;

}

-------

위 알고리즘은 똑같은 식을 계산하는 불필요한 과정이 계속 발생한다.

fibonacci(6) = fibonacci(5) + fibonacci(4) = fibonacci(4) + fibonacci(3) + fibonacci(3) + fibonacci(2) ...

fibonacci(4) 값을 2번 , fibonacci(3) 을 2번 .. 등등 알고리즘 동작시간이 증가한다.

=> 따라서 동적계획법을 이용하여 알고리즘을 다시 짜보자.

-------

< 피보나치수열 & 동적계획법 알고리즘 >

#include<stdio.h>

#include<stdlib.h>
int fibonacci_dp ( n ) {

// 인트형포인터배열

int* point = NULL ;

int i = 0 ;

if ( n == 0 ) {

return 0 ;

}else if ( n == 1 ){

return 1;

}

// 메모리 할당

point = ( int* )malloc( sizeof(int) * n ) ;

if ( point != NULL ){

point[0] = point[1] = 1;

for ( i = 2 ; i < n ; i++){

point[n] = point[n-1] + point[n-2] ;

}

result = point[ n-1 ];

free(point);

}

return result ;

}

인트형배열 point

=> 0 1 1 2 3 5 8 ... 

fibonacci[3] 값이 point[2] 에 들어있다.

fibonacci[n] == point[n-1]

동적계획법을 사용하면 불필요한 과정을 생략할 수 있다.

=> 따라서 알고리즘 성능은 향상된다.