[Algorithm] 동적계획법(Dynamic Programming)과 재귀함수(Recursion)를 통해 피보나치 수열 구하기
n번째 피보나치 수열을 동적계획법 그리고 재귀함수를 통해서 각각 구현해보자
환경
- C, C++
- 동적계획법(Dynamic Programming)에 대한 이해
- 재귀함수(Recursion)에 대한 이해
재귀함수란?
재귀함수: 재귀함수란 자신의 함수를 재호출하여 실행하는 함수를 의미합니다. 주로 분할정복과 같이 문제를 작은 부분으로 나누어서 문제를 해결할 때 많이 사용합니다.
동적계획법이란?
동적계획법(DP): 동적계획법이란 문제를 작게 쪼개서 작은 문제부터 하나하나 해결한 해를 통해 모아서 큰 문제를 해결하는 방법을 의미합니다.
재귀함수(Recursion)로 구하기
Top-down방식: 큰 문제를 작은 문제로 나누면서 해결하는 방식
fibonacci_by_recursion.c
#include <stdio.h>
int fibonacci_recursion(int n){
if (n == 0){
return 1;
}
else if(n == 1){
return 1;
}
else{
return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);
}
}
int main(){
int i;
for(i=0; i<20; i++){
printf("%d ",fibonacci_recursion(i));
}
printf("\n");
return 0;
}
동적계획법(Dynamic Programming)으로 구하기
Bottom-up방식: 작은 문제부터 하나씩 해결해 올라가는 방식
fibonacci_by_dp.c
#include <stdio.h>
int dp_array[100];
void fibonacci_dp(int n){
int i;
dp_array[0] = 1;
dp_array[1] = 1;
for(i=2; i< n; i++){
dp_array[i] = dp_array[i-1] + dp_array[i-2];
}
}
int main(){
int i;
fibonacci_dp(20);
for(i=0; i<20; i++){
printf("%d ", dp_array[i]);
}
printf("\n");
return 0;
}