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

1. 다이나믹 프로그래밍(Dynamic Programming)이란?

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장하여 다시 계산하지 않는다.
• 다이나믹 프로그래밍의 구현은 일반적으로 Top-Down, Bottom-Up 두 방식으로 구성된다.
  • Top-Down(하향식) : 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하여 작은 문제가 모두 해결될 때 큰 문제에 대한 답이 얻어지는 방식. 재귀 함수로 구현한다. (== 메모이제이션)
  • Bottom-Up(상향식) : 아래에서부터 작은 문제를 하나씩 해결해나가면서 먼저 계산한 작은 문제들의 값을 활용해 다음 큰 문제를 해결해 나가는 방식. 반복문으로 구현한다.
• 동적 계획법이라고도 부른다.

2. 다이나믹 프로그래밍의 조건

• 최적 부분 구조
  : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있어야 한다.
• 중복되는 부분 문제
  : 동일한 작은 문제를 반복적으로 해결해야 한다.

3. 메모이제이션(Memoization)

• 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
  • 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 한다.

4. 다이나믹 프로그래밍 예시

✔️ 피보나치 수열

피보나치 수열은 앞의 두 수의 합이 그 다음 수와 같은 형태로 진행되는 수열을 말하며, 위와 같은 점화식으로 표현할 수 있다.

• Top-Down 방식 (메모이제이션)

int dp[11];

int fibo(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else
	{
		// 이미 계산한 적 있는 문제라면 그대로 반환
		if (dp[n] != 0)
			return dp[n];
		// 아직 계산하지 않은 문제라면 점화식에 따라 함수 재귀 호출하고, 계산 값을 메모이제이션
		else
		{
			dp[n] = fibo(n - 1) + fibo(n - 2);
			return dp[n];
		}
	}
}

int main()
{
	cout << fibo(10);
}

• 메모이제이션 동작 분석
  • 메모이제이션 방식을 이용하면 색칠된 노드에 대해서만 재귀 실행된다.
    • f(1), f(2)는 곧바로 1을 반환
    • f(3), f(4)가 처음 계산될 때 그 결과값을 dp에 저장해두고, 이후 호출되는 f(3), f(4)에 대해서는 dp에 저장된 값을 바로 꺼내서 사용하면 재귀 실행하지 않아도 된다.
      ➡️ 실행시간 단축 가능

• Bottom-Up 방식

using namespace std;
int dp[11];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	// 반복문으로 피보나치 함수를 구현
	for(int i = 0; i <= 10; i++)
	{
		if (i == 0)
			dp[i] = 0;
		else if (i == 1)
			dp[i] = 1;
		else
			dp[i] = dp[i - 1] + dp[i - 2];
	}

	cout << dp[10];
}