동적 계획법

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <windows.h>
using namespace std;

// 동적 계획법 (DP)

// memoization
int cache[50][50];

// n개에서 r개를 추출할 경우의 수를 계산하는 함수
int combination(int n, int r)
{
	// 0개를 뽑을 경우 및 n개에서 n개를 뽑을 경우 경우의 수는 1개이다. 
	if (r == 0 || n == r)
		return 1;

	// 이미 답을 구한 적 있으면 바로 반환
	int& ret = cache[n][r];
	if (ret != -1)
		return ret;

	// 새로 답을 구해서 캐시에 저장
	return ret = combination(n - 1, r - 1) + combination(n - 1, r);
}
// 재귀 함수를 하게되면 중복계산이 발생하므로 이를 우회하거나 막는다면, 효율적인 계산이 가능하다.

int main()
{
	::memset(cache, -1, sizeof(cache));

	__int32 start = GetTickCount64();

	int lotto = combination(45, 6);

	__int32 end = GetTickCount64();

	cout << lotto << endl;
	cout << end - start << " ms" << endl;
}

 

 

응용

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <windows.h>
using namespace std;

// 동적 계획법 (DP)
// LIS (Longest Increasing Sequence)

// Seq : 1 9 2 5 7
// 부분 수열 : 일부(0개 이상) 숫자를 지우고 남은 수열
// ex_ 1 2 5
// ex_ 1 9 5 7 
// 순 증가 부분 수열
// ex_ 1 2 5 (o)
// ex_ 1 9 5 7 (x)

// Q) LIS : 제일 긴 [순 증가 부분 수열]의 길이
// 정답_ 1 2 5 7  길이 4

vector<int> seq;
int cache[100];

int LIS(int s_idx)
{
	int& ret = cache[s_idx];
	if (ret != -1)
		return ret;

	// 최소 seq[pos]는 있으니 1부터 시작
	ret = 1;

	for (int next = s_idx+1; next<seq.size();next++)
	{
		if (seq[s_idx] < seq[next])
		{
			ret = max(ret, 1 + LIS(next));
		}
	}
	return ret;
}

int main()
{ 
	::memset(cache, -1, sizeof(cache));
	seq = vector<int>{1,9,2,5,7};
	int ret;
	for (int i = 0; i < seq.size(); i++)
	{
		ret = max(ret, LIS(i));
	}
}

 

 

응용 #2

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <windows.h>
using namespace std;

// 동적 계획법 (DP)
// TRIANGLE_PATH
//	(0,0)부터 시작해서 아래 OR 아래우축으로 이동 가능
//  만나는 숫자를 모두 더함
//  더한 숫자가 최대가 되는 경로의 합은?

//	6 
//	1 2
//	3 7 4
//	9 4 1 7 
//	2 7 5 9 4

int N;
vector<vector <int>> board;
vector<vector <int>> cache;
vector<vector <int>> nextX;

int path(int y, int x)
{
	//기저 사항
	if (y == N - 1)
		return board[y][x];	

	//캐시 확인
	int& ret = cache[y][x];
	if (ret != -1)
		return ret;
	// 경로 기록
	{
		int nextBottom = path(y + 1, x);
		int nextBottomRight = path(y + 1, x + 1);
		if (nextBottom > nextBottomRight)
			nextX[y][x] = x;
		else
			nextX[y][x] = x + 1;
	}

	ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));

	return ret;
}

int main()
{ 
	board = vector<vector<int>>
	{
		{6},
		{1,2},
		{3,7,4},
		{9,4,1,7},
		{2,7,5,9,4},
	};
	N = board.size();
	cache = vector<vector<int>>(N, vector<int>(N, -1));
	nextX = vector<vector<int>>(N, vector<int>(N));


	int ret = path(0, 0);
	cout << ret << endl;
	int x = 0;
	int y = 0;
	while (y<N)
	{
		cout << board[y][x] << "->";

		x = nextX[y][x];
		y++;
	}
}