011_동적 계획법 (DP)

동적 계획법

동적 계획법(Dynamic Programming)은 동일한 문제를 다시 풀지 않도록, 처음으로 한 번 문제를 풀었을 때 그 결과를 저장해두고, 동일한 문제를 만나면 저장한 데이터를 가져오는 알고리즘이다.

불필요한 반복적인 계산을 줄이고, 효율적으로 최적해를 찾는다.

메모이제이션(Memoization) 기법이라 볼 수 있는데, 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

메모리를 내어누고 시간을 버는 방법이라 볼 수 있다.

동적 계획법을 이용해 문제를 풀 경우 점화식을 세운다. 점화식이란 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식으로 피보나치 수열을 예로 들면 다음과 같다.

위 점화식을 이용해 피보나치 수열을 일반적인 재귀를 통해 구현하면 다음과 같다.

#include <iostream>

int Fibonacci(int Num)
{
	if (1 == Num || 0 == Num)
		return 1;
	
	return Fibonacci(Num - 1) + Fibonacci(Num - 2);
}

이때 피보나치 수열의 6번째 항을 구한다고 가정하면, 컴퓨터는 아래 작업들을 수행하게 된다.

그림을 보면 Fibonacci(2), Fibonacci(1), Fibonacci(0) 의 해를 구하는 과정을 여러번 반복하는 것을 볼 수 있다. 만약 구하려는 수가 커질수록 이러한 중복 과정이 기하 급수적으로 증가 하게 된다.

이럴때 동적 계획법을 이용할 수 있다.

구현 방법

우선 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- 큰 문제들은 작은 문제들로 이루어진다. 즉, 작은 문제들로 분할이 가능하다.
- 단, 큰 문제와 작은 문제의 관계에서 사이클이 발생해선 안된다.
작은 문제에서 구한 정답은 큰 문제에서도 동일하다.
- 즉, 점화식을 세울 수 있어야 한다.
- N = 4 를 구하는 과정에서 저장한 N = 3 의 정답을, N = 5 에서도 그대로 쓸 수 있어야한다.

위의 가정이 충족된다면 동적 계획법을 구현하는 방법에는 크게 두가지가 있다.

Top-Down 방식 큰 문제를 작은 문제로 쪼개 나간다. 재귀를 이용해 구현할 수 있다.
Bottom-Up 방식 작은 문제부터 올라간다. 반복문을 이용해 구현할 수 있다.

예시

피보나치 수열

F(N) = F(N - 2) + F(N - 1), (N > 1)

Top-down 방식

#include <iostream>
#include <vector>

int Fibonacci(std::vector<int>& Arr, int K)
{
	// 초기 조건
	if (1 >= K) 
	{
		Arr[K] = K;
		return Arr[K];
	}

	// 이미 값을 구한 경우 구한 값 사용
	if (-1 != Arr[K])
		return Arr[K];

	// 값 구하기
	Arr[K] = Fibonacci(Arr, K - 2) + Fibonacci(Arr, K - 1);
	return Arr[K];
}

int main()
{
	int N = 5;
	std::vector<int> Temp(N + 1, -1);
	std::cout << Fibonacci(Temp, N);
	return 0;
}

Bottom-up 방식

#include <iostream>
#include <vector>

int Fibonacci(int N)
{
	// 초기 조건
	std::vector<int> Fibo(N + 1, 0);
	Fibo[0] = 0, Fibo[1] = 1;

	// 값 구하기
	for (int i = 2; i <= N; i++)
		Fibo[i] = Fibo[i - 2] + Fibo[i - 1];

	return Fibo[N];
}

int main()
{
	std::cout << Fibonacci(5);
	return 0;
}