천천히 빛나는
알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (2) - 기초 문제 풀이 (C++로 구현) 본문
알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (2) - 기초 문제 풀이 (C++로 구현)
까만콩 •ᴥ• 2023. 10. 20. 03:461. 개미 전사
개미 전사를 위해 식량창고 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 함수를 사용하는 것이 핵심이다.
'STUDY > ALGORITHM' 카테고리의 다른 글
알고리즘 : 최단 경로 알고리즘 (2) - 플로이드 워셜 알고리즘 (0) | 2024.02.23 |
---|---|
알고리즘 : 최단 경로 알고리즘 (1) - 다익스트라(Dijkstra) 알고리즘 (Java로 구현) (0) | 2024.02.23 |
알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (1) (0) | 2023.10.19 |
알고리즘 : 백트래킹 (Back-tracking) + 조합, 순열 (C++ 구현) (0) | 2023.10.09 |
알고리즘 : DFS와 BFS (3) - 기초 문제 풀이 (C++로 구현) (0) | 2023.10.07 |