알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (2) - 기초 문제 풀이 (C++로 구현)

1. 개미 전사

 

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하는 문제이다.

 

N=4일 때 식량을 선택할 수 있는 경우의 수는 8가지이다. 최적의 해는 7번째(3+5=8)가 된다.

a_i를 i번째 식량창고까지의 최적의 해라고 정의하도록 하겠다.

 

i번째 식량창고에 대해서 털지 안 털지의 여부를 결정하기 위해서는 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 

 

int n;
int food[101];
int dp[101];
int main() {
	cin >> n;
	for (int i = 1; i <=n; i++)
	{
		cin >> food[i];
	}
	dp[1] = food[1];
	dp[2] = max(food[1], food[2]);
	for (int i = 3; i <= n; i++)
	{
		dp[i] = max(dp[i - 2] + food[i], dp[i - 1]);
	}
	cout << dp[n];
	return 0;
}

보텀업 방식으로 반복문을 이용해서 구현하였다.

 

 

2. 1로 만들기

 

void dfs(int x, int cnt) {
	if (x == 1) {
		if (minVal > cnt) 
			minVal = cnt;
		return;		
	}
	if (x % 5 == 0)
		dfs(x / 5, cnt + 1);
	if (x % 3 == 0)
		dfs(x / 3, cnt + 1);
	if (x % 2 == 0)
		dfs(x / 2, cnt + 1);
	dfs(x - 1, cnt + 1);
}

void with_DP(int x) {
	vector<int>temp;
	if (x % 5 == 0)
		temp.push_back(dp[x / 5] + 1);
	if (x % 3 == 0)
		temp.push_back(dp[x / 3] + 1);
	if (x % 2 == 0)
		temp.push_back(dp[x / 2] + 1);
	temp.push_back(dp[x - 1] + 1);
	sort(temp.begin(), temp.end());
	dp[x] = temp[0];
}

int main() {
	cin >> X;
	dp[1] = 0;
	for (int i = 2; i <= X; i++)
	{
		with_DP(i);
	}
	cout << dp[X] << '\n';

	dfs(X, 0);
	cout << minVal << '\n';
	return 0;
}

완전탐색이랑 DP 모두 구현해보았다. 입력해보면 알겠지만 큰 값을 입력했을 때 DP 함수 값은 아주 빠르게 출력되지만 완전탐색으로 구현한건 오래걸린다. 1000만 입력해봐도 알 수 있다.

 

3. 효율적인 화폐 구성

화폐의 개수를 최소한으로 하여 합이 M원이 되도록 하는 문제이다.

 

a_i를 금액 i를 만들 수 있는 최소한의 화폐 개수라고 하겠다. 

 

int N, M;
vector <int> money;
int dp[100];
void findMoney(int x) {
	vector<int>v;
	for (int i = 0; i < N; i++)
	{
		if (x - money[i] > 0 && dp[x - money[i]] > 0)
			v.push_back(dp[x - money[i]] + 1);
	}
	if (v.size() != 0) {
		sort(v.begin(), v.end());
		dp[x] = v[0];
	}
	else if (dp[x] == 0) {
		dp[x] = -1;
	}
}

void greedy() {
	int temp = M;
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		cnt += temp / money[i];
		temp %= money[i];
		if (temp == 0)
			break;
	}
	if (temp != 0)
		cout << -1;
	else
		cout << cnt;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int x;
		cin >> x;
		money.push_back(x);
		dp[x] = 1;
	}
	for (int i = 1; i <= M; i++)
	{
		findMoney(i);
	}
	cout << dp[M];
	
	sort(money.begin(), money.end(), greater<>());
	greedy();
	return 0;
}

그리디랑 DP로 풀 수 있는 문제이다. 그리디로 풀 경우 내림차순으로 정렬해주는 것을 잊으면 안된다.

 

 

4. 금광

 

금광의 모든 위치에 대하여 세 가지 방향을 고려해서 코드를 구현해야한다.

 

왼쪽 위에서 오는 경우, 왼쪽 아래에서 오는 경우, 왼쪽에서 오는 경우 중에 최대값에 현재 내 위치의 금을 더해주면 된다.

 

dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

가장 오른쪽 열에 오는 최대값이 문제의 정답이 될 것이다.

#include<iostream>
using namespace std;
int testCase, n, m;
int arr[20][20];
int dp[20][20];
int main() {
	cin >> testCase;
	for (int tc = 0; tc < testCase; tc++)
	{
		cin >> n >> m;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> arr[i][j];
			}
		}

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				dp[i][j] = arr[i][j];
			}
		}

		for (int j = 1; j < m; j++)
		{
			for (int i = 0; i < n; i++)
			{
				int leftUp, leftDown, left;
				// 왼쪽 위
				if (i == 0)
					leftUp = 0;
				else
					leftUp = dp[i - 1][j - 1];
				// 왼쪽 아래
				if (i == n - 1)
					leftDown = 0;
				else
					leftDown = dp[i + 1][j - 1];
				left = dp[i][j - 1];
				dp[i][j] = dp[i][j] + max({ left, leftDown, leftUp });
			}
		}

		int result = 0;
		for (int i = 0; i < n; i++)
		{
			result = max(result, dp[i][m - 1]);
		}
		cout << result;
	}
}

식을 세운 후 DP를 이용해 구현할 수 있다.

 

 

5. 병사 배치하기

DP 문제 중 잘 알려진 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)이다. 예를 들어 하나의 수열 {4, 2, 5, 8, 4, 11, 15}가 있다고 할 때 이 수열의 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15}이다. 이 문제는 가장 긴 감소하는 부분 수열을 찾는 문제이므로 LIS 알고리즘을 조금 수정하면 구현할 수 있을 것이다.

 

 

가장 긴 증가하는 부분 수열 (LIS) 알고리즘

D[i] : arr[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

모든 0<=j<i에 대하여, 만약 arr[j] < arr[i]라면 D[i] = max(D[i], D[j]+1) 

 

부분 수열을 만들 때 각 원소 하나만 가지고 만들면 길이가 1이 되므로 모두 1로 초기화를 해준다.

 

4가 2보다 크기 때문에 값이 갱신되지 않고 그대로 남게 된다.

4보다 5가 크기 때문에 비교해서 더 큰 값이 들어가도록 한다. 또한 2보다 5가 크기 때문에 비교해서 더 큰 값이 들어가도록 한다.

최종적으로 남아있는 값에서 최대값이 정답이 된다.

 

int n;
vector<int> v;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}

	reverse(v.begin(), v.end());
	int dp[2000];
	for (int i = 0; i < n; i++)
	{
		dp[i] = 1; // 초기화
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[j] < v[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	int maxVal = 0;
	maxVal = *max_element(begin(dp), dp + n);
	cout << n - maxVal << '\n';
}

주어진 문제를 해결하기 위해서는 순서를 뒤집어서 LSI 문제와 똑같이 구현을 하면 된다. c++에서는 reverse 함수를 사용하는 것이 핵심이다.