🧑🏻💻
알고리즘 박살내기 - 29 - 2. 다이나믹 프로그래밍 기초 문제 풀이 (2)
May 13, 2022
Introduction
본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다.
효율적인 화폐 구성
문제 설명
- N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M 원이 되도록 하려고 합니다. 이때 각 종류의 화폐는 몇 개라도 사용할 수 있습니다.
- 예를 들어 2원, 3원 단위 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수 입니다.
- M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요.
문제 조건
- 난이도 : 중상
- 풀이시간 : 30분
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건 :
- 첫째 줄에 N, M이 주어진다. (1<= N <= 100, 1 <= M <= 10,000)
- 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.
- 출력 조건 :
- 첫째 줄에 최소 화폐 개수를 출력한다.
- 불가능 할 때는 -1 을 출력한다.
- 입출력 예시 :
# 입력 예시 1 2 15 2 3 # 출력 예시 1 5 # 입력 예시 2 3 4 3 5 7 # 출력 예시 2 -1
문제 해결 아이디어
-
𝑎ᵢ = 금액 𝒊를 만들 수 있는 최소한의 화폐 개수
-
𝒌 = 각 화폐의 단위
-
점화식 : 각 화폐 단위인 𝒌를 하나씩 확인하며
- a_{i - k} 를 만드는 방법이 존재 하는 경우 𝑎ᵢ = min(aᵢ, a_{i - k} + 1)
- a_{i - k} 를 만드는 방법이 존재하지 않은 경우 𝑎ᵢ = INF
-
N = 3, M = 7, 화폐 단위가 2, 3, 5인 경우 확인해봅시다.
-
step 0
- 각 인덱스에ㅎ 해당하는 값으로 INF의 값을 설정합니다.
- INF는 특정 금액을 만 들 수 있는 화폐 구성이 가능하다는 의미를 가집니다.
- 본 문제는 10,001을 사용할 수 있습니다. 이렇게 한 이유는 만들 수 있는 최대의 금액이 10,000이고, 화폐 최소 단위 1을 기준으로 1만개로 만들 수있는 값(MAX)의 1 더한 값으로, 기준 범위를 초과한 INF값으로 설정할 수 있습니다.
인덱스 값 0 1 2 3 4 5 6 7 값 0 10001 10001 10001 10001 10001 10001 10001 -
step 1
- 첫 번째 화폐 단위가 2를 확인합니다.
- 점화식에 따라서 다음 리스트 값들이 갱신 됩니다.
인덱스 값 0 1 2 3 4 5 6 7 값 0 10001 1 10001 2 10001 3 10001 - 2원은 1개로 만들 수 있음
- 4원은 2원 2개로 만들 수 있음
- 나머지 값들 중 만들 수 없는 것들에 대해선 그대로 INF 상태를 둔다.(따라서 7원도 만들 수 없다.)
-
step 2
- 두 번째 화폐 단위인 3를 확인합니다.
인덱스 값 0 1 2 3 4 5 6 7 값 0 10001 1 1 2 2 2 3 - 5원 만들기 위한 개수 : 2개 (2원 + 3원)
- 7원 만들기 위한 개수 : 3개 (2원 + 2원 + 3원)
-
step 3
- 세 번째 화폐 단위인 5를 확인한다.
인덱스 값 0 1 2 3 4 5 6 7 값 0 10001 1 1 2 1 2 3 - 7원 만들기 위한 개수 : 2원 + 5원
답안 예시(Python)
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# DP 테이블 작성 및 초기 값으로 INF 값을 작성하기
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(보텀업)
d[0] = 0
for i in range (n):
for j in range (array[i], m + 1):
if d[j - array[i]] != 10001:
d[j] = min(d[j]. d[j - array[i]] + 1)
# 결과 출력 시 해당 금액이 INF로 만드는 방법이 없는 경우
if d[m] == 10001:
print(-1)
else :
print(d[m])답안 예시(C++)
#include <bit/stdc++.h>
using namespace std;
int n, m;
vector<int> arr;
int main(void)
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
arr.push_back(x);
}
vector<int> d(m + 1, 10001);
d[0] = 0;
for (int i = 0; i < n; i++)
for (int j = arr[i] != 10001)
{
if (d[j - arr[i] != 10001])
d[j] = min(d[j], d[j - arr[i]] + 1);
}
if (d[m] == 10001)
cout << -1 <<'\n';
else
cout << d[m] << '\n';
}금광
문제 설명
- n × m 크기의 금광이 있습니다. 금광은 1 × 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정 크기의 금이 들어 있습니다.
- 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번재 열의 어느 행에서든 출발할 수 있스빈다. 이후 m - 1번에 걸쳐서 매번 오른 쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.
| 1 | 3 | 3 | 2 |
|---|---|---|---|
2 |
1 | 4 | 1 |
| 0 | 6 |
4 |
7 |
➡︎ 얻을 수 있는 최대 금의 크기 : 19
문제 조건
- 난이도 : 중하
- 풀이시간 : 30분
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 기출 : Flipkart 인터뷰
- 입력 조건 :
- 첫째 줄에 테스트 케이스 T가 입력됩니다.(1 <= T <= 1000)
- 매 테스트 케이스 첫번째 줄에 n, m이 공백으로 구분되 입력됩니다.(1 <= n, m <= 20)
- 둘 째 줄에는 n × m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다.(1 <= 각 위치 매장된 금 개수 <= 100)
- 출력 조건 : 테스트 케이스 마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스 마다 줄 바꿈을 이용해 구분합니다.
- 입출력 예시 :
# 입력 예시 2 3 4 1 3 3 2 2 1 4 1 0 6 4 7 4 4 1 3 1 5 2 2 4 1 5 0 2 3 6 1 2 # 출력 예시 19 16
문제 해결 아이디어
-
금광의 모든 위치에 대해선 다음의 세가지 경우만 고려 됩니다.
- 왼쪽 위
- 왼쪽 아래
- 왼쪽 중간에서 오는 경우
-
따라서 세가지 경우 중 가장 많이 금을 가지는 경우 + 현재 위치의 금 값으로 테이블을 갱신해주는 방식으로 최대 값을 구할 수 있습니다.
↘︎ ☐ ☐ → ⭐️ ☐ ↗︎ ☐ ☐ -
array[i][j] = i행 j열에 존재하는 금의 양
-
dp[i][j] = i행 j열까지의 최적의 해(얻을 수 있는 금의 최댓값)
-
점화식 :
- 단, 테이블 접근 시 리스트 범위를 벗어나지 않도록 체크합니다.
- 편의상 초기 데이터를 담는 변수 array를 사용하지 않고 dp 테이블에 초기 값을 담아 사용해도 됩니다.
- 그림으로 확인해보는 금광 문제 해결 과정
| 1 | 3 | 3 |
|---|---|---|
| 2 | 1 | 4 |
| 0 | 6 | 4 |
| 1 | 5 |
☐ |
|---|---|---|
| 2 | 3 |
☐ |
| 0 | 8 |
☐ |
.
.
(반복)
답안 예시(Python)
# 테스트 케이스 횟수에 따라 반복
for tc in range(int(intput())):
n, m = map(int, input().split())
array = list (map(int, input().split()))
# dp 테이블 작성
dp = []
index = 0;
for i in range(n):
dp.append(array[index:index + m])
index += m
# 다이나믹 프로그래밍 진행
for j in range (1, m):
for i in rnage(n):
# 왼쪽 위에서 오는 경우 구분
if i == 0:
left_up = 0
else:
left_up = dp[i - 1][j - 1]
# 왼쪽 아래에서 오는 경우 구분
if i == n - 1:
left_down = 0
else:
left_down = dp[i + 1][j - 1]
# 어느 위치든 왼쪽 중간 위치는 신경 쓰지 않아도 됨
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left, left_down)
result = 0
for i in range(n)
result = max(result, dp[i][m - 1])
print(result)답안 예시(C++)
#include <bits/stdc++.h>
using namespace std;
int testCase, n, m;
int arr[20][20];
int dp[20][20];
int main(void)
{
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(leftUp, max(leftDown, left));
}
}
int result = 0;
for (int i = 0; i < n; i++)
result = max(result, dp[i][m - 1]);
cout << result << '\n';
}병사 배치하기
문제 설명
- N명의 병사가 무작위로 나열되어 있습니다. 각 병사는 특정한 값의 전투력을 보유하고 잇습니다.
- 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 합니다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽 병사보다 높아야 합니다.
- 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외 시키는 방법을 이용합니다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고 싶습니다.
- 예를 들어 N = 7일 때 나열된 병사들의 전투력은 다음과 같다고 가정합니다.
병사 번호 1 2 3 4 5 6 7 전투력 15 11 4 8 5 2 4 - 이때 3번, 6번 만 열외하면 남아 있는 병사의 수가 내림차순의 형태가 되며 5명이 남게 됩니다. 이는 남아 있는 병사가 최대가 되면서도 내림차순으로 정렬된 형태입니다.
병사 번호 1 2 4 6 7 전투력 15 11 8 5 4 - 병사에 대한 정보가 주어질 때, 남아 있는 병사 의 수가 최대가 되도록 하기 위해 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하세요.
문제 조건
- 난이도 : 중하
- 풀이시간 40분
- 시간 제한 : 1초
- 메모리 제한 : 256MB
- 기출 : 핵심 유형
- 입력 조건 :
- 첫째 줄에 N이 주어집니다(1<= N <= 2,000)
- 둘째 줄에 각 병사의 전투력이 공백으로 구분되어 차례대로 주어집니다. 전투력은 10,000,000보다 작거나 같은 자연수입니다.
- 출력 조건 : 첫째 줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외 시켜야 하는 병사의 수를 출력합니다.
- 입출력예시 :
# 입력 예시 7 15 11 4 8 5 2 4 # 출력 예시 2
문제 해결 아이디어
-
이 문제의 기본 아이디어는 최장증가부분수열(Longest Increasing Subsequence, LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같습니다.
-
예를 들어 하나의 수열 arr = {4, 2, 5, 8, 4, 11, 15}가 있다고 합시다. 여기서 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15} 입니다.
-
해당 문제에선 가장 긴 감소하는 부분 수열을 찾는 문제로 치환 할 수 있으므로 LIS 알고리즘을 수정 적용함으로써 정답을 도출 할 수 있습니다.
-
최장증가부분수열(LIS) 알고리즘을 확인하여 사용하면 됩니다.
-
D[i] = array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이
-
점화식
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 |
1 | 1 | 1 | 1 | 1 |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 |
1 | 1 | 1 | 1 |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 |
1 | 1 | 1 |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 2 |
1 | 1 |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 2 | 4 |
1 |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 2 | 4 | 5 |
- 최종적으로 DP 테이블에 남아있는 값중 가장 큰 값인 것을 발견하면, LIS가 가장 긴 경우인 것이라고 볼 수 있습니다.
- 그러나 최장감부분수열(LIS)알고리즘 형태가 되어야 하므로, 먼저 입력 받은 병사의 정보 순서를 뒤집어 계산을 한 뒤, 그 값을 전체 인원 수에서 빼서 정답을 도출 할 수 있습니다.
답안 예시(Python)
# 초기 값 받기
n = int(input())
array = list(map(int, intpu().split()))
# 리스트 뒤집어 LIS 배열 만들기 위한 준비
array.reverse()
# DP 테이블 초기화
dp = [1] * n
#LIS 알고리즘
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
#열외 병사를 구하는 것이므로
print(n - max(dp))답안 예시(C++)
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
int main(void)
{
cint >> 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 maxValue = 0;
for (int i = 0; i < n; i++)
maxVlaue = max(maxValue, dp[i]);
cout << n - maxValue << '\n';
}