다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘?

 

다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있습니다.

 

1번. 큰 문제를 작은 문제로 나눌 수 있습니다.

2번. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다.

 

그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다.

--> 분할 정복과 애매하게 다른 느낌이다?

이 과정에서 메모이제이션이 사용된다는 점에서 다르다고 합니다.

--> 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 되는 것.

 

대표적으로 피보나치 수열을 문제로 다이나믹 프로그래밍으로 해결해본다.

#include <stdio.h>

int d[100];

long long dp(int x)
{
	if (x == 1) return 1;
	if (x == 2) return 1;
	//연산 횟수 2^50....

	if (d[x] != 0) return d[x];


	return d[x] = dp(x - 1) + dp(x - 2);
}

int main(void)
{
	printf("%lu\n", dp(30));
	
	return 0;
}