Dynamic-programming(동적기획법)

 

 

: Dynamic-programming 알고리즘을 사용하는 대표적인 예로는 피보나치 수열이 있다

 

 

(1) dynamic-programming(top-down, memoization)

피보나치 수열을 구현하는 방법은 순환 호출과 반복문을 사용하는 방법이 있는데 순환 호출을 사용할 경우 예를 들어 int fibo(int num)이라는 함수를 호출하게 되면 같은 함수를 중복해서 호출하는 경우가 생기기에 비효율적이다.

ex) fibo(6)

                                      fibo(6)

                  fibo(4)                                    fibo(5) 

      fibo(2)             fibo(3)               fibo(3)              fibo(4)

fib(2) fibo(3)     fibo(1) fibo(2)    fibo(1) fibo(2)   fibo(2) fibo(3)

 

=> 중복호출되는 함수들이 존재

=> num값이 커질수록 중복현상은 더 심해짐

=>이를 보완하고자 dynamic-programming(동적기획법)알고리즘이 생겨남

=>top-down(memoization)이라고도 함

=>호출함수와의 차이점은 '계산된 값을 재사용 하느냐'이다

=>배열을 이용해 구현

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

//피보나치 수열 0 1 1 2 3 5 ... 로 가정

int top_down(int num) {
	int* valfibo = NULL;
	valfibo = (int*)calloc(num, sizeof(int));
	assert(valfibo != NULL);
	int i = 0;
	valfibo[i++] = 0;
	valfibo[i++] = 1;

	if (valfibo[num] != 0) {
		return valfibo[num];
	}
	else {
		valfibo[num] = top_down(num - 1) + top_down(num - 2);
		return valfibo[num];
	}
	
}

void top_down_test() {
	int num;
	int result;
	printf("몇 번째항의 피보나치 수열을 구할까요?\n");
	scanf("%d", &num);

	result = bottom_up(num);
	printf("피보나치 수열의 %d번째 항은 %d입니다.", num, result);


}

int main(){
  top_down_test();
  
  getchar();
  return 0;
}

=> 하지만 재귀호출의 overflow 발생 가능성이 있기에 반복문을 사용하는 것이 더 좋은 방법이다.

 

(2) 반복문(bottom-up)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

//피보나치 수열 0 1 1 2 3 5 ... 로 가정

int bottom_up(int num) {
	int first = 0;
	int second = 1;
	int i;
	int res = 0;
	if (num == 1) {
		return 0;
	}
	else if (num == 2) {
		return 1;
	}
	else {
		for (i = 3; i <= num; i++) {
			res = first + second;
			first = second;
			second = res;
		}
	}
	return res;
}

void bottom_up_test() {
	int num;
	int result;
	printf("몇 번째항의 피보나치 수열을 구할까요?\n");
	scanf("%d", &num);

	result = bottom_up(num);
	printf("피보나치 수열의 %d번째 항은 %d입니다.", num, result);
}

int main() {
	bottom_up_test();
	

	getchar();
	return 0;
}