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

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

 

다이나믹 프로그래밍이란?

 

 - 큰 단위의 문제를 작은 단위로 나누고, 작은 단위 문제부터 처리한다.

   큰 단위의 문제를 해결하기 위하여 기존에 처리했던 작은 단위의 문제를 이용한다.

 

 - 작은 단위의 문제를 풀다보면 반복적인 작업이 많이 발생하는데, 이를 해결하기 위하여 

   메모이제이션이라는 기법을 이용한다.

 

 - 메모이제이션 : 기존에 처리했던 문제를 저장한 후, 같은 문제를 처리해야 할 때 다시 문제를 처리하는 것이 아니라

   기존에 저장된 값을 사용하는 것.

 

 

---

 

다이나믹 프로그래밍 방법

 

 1. 문제를 완전 탐색으로 풀어야하는데 경우의 수가 너무 많아서 시간내에 불가능하다.

 

 2. 문제의 상태를 살펴보고, 공통적인 부분을 도출하여 묶어준다.

 

 3. 메모이제이션으로 적용할 DP 테이블을 문제에 맞게 정의한다. 

 

 4. DP 테이블의 초기 값을 설정한다.

 

 5. 주어진 문제를 작은 단위로 쪼개서 빠르게 풀 수 있는지 확인한다.

 

 6. DP 테이블을 이용하여 정답을 출력한다

 

 

 

---

다이나믹 프로그래밍 예시

 

 - 다이나믹 프로그래밍의 대표적인 예시 피보나치 수열 구하기.

 

 - 피보나치 수열 점화식

 

 

- F(5)를 구하기 위해서는 F(1), F(2), F(3)가 여러번 반복된다.

 

 

- 메모이제이션을 이용하면 위 표시되어 있는 중복된 부분은 저장된 값을 이용하기 때문에 반복 계산이 일어나지 않는다..

 

 

 

---

 

다이나믹 프로그래밍 코드(C++)

// DP를 사용하지 않는 경우

#include <bits/stdc++.h>

using namespace std;

int fibo(int result)
{
	cout << "fibo(" << result << ") 계산 \n";

	if (result <= 2)
		return 1;

	return fibo(result - 1) + fibo(result - 2);;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cout << "fibo(5) : " << fibo(5) << endl;


	return 0;
}

---

 

// DP 사용하는 경우

#include <bits/stdc++.h>

using namespace std;

int memo[6];

int fibo(int result)
{
	cout << "fibo(" << result << ") 실행 \n";

	int num = 0;
	
	if (result <= 2)
	{
		return 1;
	}
	
	if (!memo[result])
	{
		memo[result] = fibo(result - 1) + fibo(result - 2);
	}
	
	return memo[result];
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cout << "fibo(5) : " << fibo(5) << endl;


	return 0;
}