[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

---

하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 피보나치 수열과 같이 한 번 푼것을 여러번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법으로 사용한다. 그리고 다이나믹 프로그래밍은 두가지 가정하에 사용할 수있는데

1) 큰 문제는 작은 문제로 나눌 수 있다.

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

즉, 다이나믹 프로그래밍은 큰 문제를 해결하기 위해서 그것을 작게 나누어 해결한 뒤 그것을 이용하여 답을 구하는 것이다. 하지만 이 과정이 분할정복과 다른 점은 메모제이션(Memozation)이 사용된다는 점이다. 이미 계산한 것을 저장하는 것으로 나중에 동일한 계산을 할 때는 저장된 값을 반환하여 사용하기만 하면 된다.

 

피보나치 수열 (Fibonacci Numbers)

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

Bad Case

#include <iostream>

using namespace std;

int FibonacciNumbers(int num)
{
	if (num == 1) return 1;
	if (num == 2) return 1;
	return FibonacciNumbers(num - 2) + FibonacciNumbers(num - 1);
}

int main()
{
	cout << FibonacciNumbers(50) << endl;
	return 0;
}

출력 결과

답이 계산되는 과정이 너무 오래 걸려서 한참을 계산 상태로 유지하고 있다.

Good Case

#include <iostream>

using namespace std;

int FNumbers[1000] = { 0 };

int FibonacciNumbers(int num)
{
	if (num == 1) return FNumbers[num] = 1;
	if (num == 2) return FNumbers[num] = 1;
	if (FNumbers[num] != 0) return FNumbers[num];
	return FNumbers[num] = FibonacciNumbers(num - 2) + FibonacciNumbers(num - 1);
}

int main()
{
	
	cout << FibonacciNumbers(48) << endl;
	return 0;
}

출력 결과

---

피보나치 수열을 일반적인 방법과 다이나믹 프로그래밍을 활용한 방법으로 구현을 해보았다. 값을 저장하기 때문에 기존에 계산했던 과정을 줄일 수 있어서 적은 숫자에서 부터 체감이 느껴졌다.