나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리한다.
(내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저'임을 사전에 밝힙니다.)
'Ch05. 다이나믹 프로그래밍 (1)'의 이론에 이어서, 다이나믹 프로그래밍 예제를 풀어보자.
https://jjuke-brain.tistory.com/75
Ch05. 다이나믹 프로그래밍 (1) (feat. 이것이 취업을 위한 코딩테스트다)
나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리한다. (내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 wi
jjuke-brain.tistory.com
강의 영상 링크는 다음과 같다.
https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6
목차
5. 다이나믹 프로그래밍 예제 - 개미 전사
Q) 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데, 식량창고는 일직선으로 이어져 있다.
각 식량창고에는 정해진 수의 식량을 저장하고 있으며, 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 것이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.
따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소 한 칸 이상 떨어진 식량창고를 약탈해야 한다.
예를 들어, 위와 같이 식량창고 4개가 존재한다고 가정하자. 이를 배열(리스트)로 나타내면 다음과 같다.
{1, 3, 1, 5}
이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을 수 있다. 개미 전사는 식량창고가 이렇게 일직선 상일 때 최대한 많은 식량을 얻기를 원한다.
개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라.
- 입력 조건
- 첫째 줄에 식량창고의 개수 N이 주어진다. (3 ≤ N ≤ 100)
- 둘재 줄에 공백을 기준으로 각 식량창고에 저장된 식량 개수 K가 주어진다. (0 ≤ K ≤ 1,000)
- 출력 조건
- 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.
1) 문제 해결 아이디어
예시에서, N = 4일 때, 다음과 같은 경우가 존재할 수 있다.
7번째 경우에서 8만큼의 식량을 얻어 최댓값을 가지므로 최적의 해는 8임을 알 수 있다.
\(a_i\)를 \(i\)번째 식량 창고까지의 최적의 해, 즉 얻을 수 있는 식량의 최댓값으로 가정하자.
이렇게 문제를 부분문제로 나눔으로써 두 가지 조건을 만족하게 되면서 다이나믹 프로그래밍을 적용할 수 있다.
왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정 \(i\)번째 식량창고에 대해 털지 안 털지의 여부를 결정하면, 아래 2가지 경우 중 더 많은 식량을 털 수 있는 경우를 선택하면 된다.
바로 앞 쪽에서 식량창고를 털었다면, 현재 식량 창고는 털 수 없는 상태이고, 바로 앞 쪽 식량창고를 털지 않았다면, 현재 식량창고를 털 수 있다.
즉, \(i\)번째까지의 식량을 얻을 수 있는 최댓값을 구하기 위해서는 '바로 앞 위치까지의 최적의 해'와 '2칸 앞 위치까지의 최적의 해에 현재 위치의 식량의 값을 더한 값'을 비교하여 더 큰 경우를 고르면 된다.
다이나믹 프로그래밍의 조건을 만족하는지 확인해보자.
\(i\)번째 까지의 최적의 해는 \(i - 1\)번째, \(i - 2\)번째까지의 최적의 해를 이용하여 계산할 수 있으므로, 최적 부분 구조를 만족한다.
즉, 큰 문제 해결을 위해 작은 문제 2개를 이용한다.
또한 작은 문제들을 해결할 때 부분 문제들을 같은 방식으로 중첩시켜 사용한다.
이때, \(i - 3\)번째 까지의 최적의 해는 이전에 이미 고려한 결과값이 존재하기 때문에 고려할 필요가 없다는 것에 주목하자.
이를 수식으로 표현하면
- \(a_i = i\)번째 식량창고까지의 최적의 해(Optimal Solution), 즉 얻을 수 있는 식량의 최댓값
- \(k_i = i\)번째 식량창고에 있는 식량의 양
와 같다.
점화식은 다음과 같다.
$$ a_i = \max(a_{i-1}, a_{i-2} + k_i) $$
한 칸 이상 떨어진 식량창고는 항상 털 수 있으므로, (\(i - 3\))번째 이하는 고려할 필요가 없다.
2) 소스 코드 (Python)
# 정수 N 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블
d = [0] * 100 # N의 최댓값
# 다이나믹 프로그래밍 진행 (Buttom-up)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + array[i])
# 계산된 결과 출력
print(d[n - 1])
3) 소스 코드 (C++)
#include <bits/stdc++.h>
using namespace std;
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d[100];
int n;
vector<int> arr;
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
// 다이나믹 프로그래밍 진행 (Buttom-up)
d[0] = arr[0];
d[1] = max(arr[0], arr[1])
for (int i = 0; i < n; i++) {
d[i] = max(d[i - 1], d[i - 2] + arr[i]);
}
cout << d[n - 1] << endl;
return 0;
}
6. 다이나믹 프로그래밍 예제 - 1로 만들기
Q) 정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
- X가 5로 나누어 떨어지면, 5로 나눈다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
X가 주어졌을 때, 연산 4개를 적절히 사용하여 값을 1로 만들고자 한다. 연산을 사용하는 횟수의 최솟값을 출력하라.
예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다.
26 → 25 → 5 → 1
- 입력 조건
- 첫째 줄에 정수 X가 주어진다. (1 ≤ X ≤ 30,000)
- 출력 조건
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
- 입력 예시 : 26
- 출력 예시 : 3
1) 문제 해결 아이디어
피보나치 수열에서와 마찬가지로, 문제를 트리 구조로 표현해보자.
매 상황마다 가능한 경우(최대 4개)에 대해 각 부분 문제를 확인해보고, 그 부분 문제들 중에서 가장 작은 값을 갖는 결과를 골라 거기에 1을 더하여 Optimal Solution 값을 찾을 수 있다.
그리고 동일한 부분 문제가 여러 번 호출되고 있는 것을 통해 중복되는 부분 문제 조건까지 만족함을 알 수 있다.
참고로 이 문제는 그리디 문제의 '1이 될 때까지'문제와는 다르다.
'1이 될 때까지' 문제에서는 값이 어떻든 간에 빼는 것보다 2 이상의 수로 나누는 것이 값을 빠르게 줄일 수 있기 때문에 매 상황마다 단순히 나누어 떨어질 때 나눌 수 있도록 하는 아이디어가 사용될 수 있었다.
하지만, 본 문제에서는 5로 나눌 수 있을 때까지 1을 빼고 나누는 것보다 다른 연산을 적절히 사용했을 경우 더 빠르게 값을 줄일 수 있는 경우가 존재할 수 있기 때문에 이 문제는 단순히 그리디 알고리즘으로 해결할 수 없다.
\(a_i = i\)를 1로 만들기 위한 최소 연산 횟수로 정의했을 때,
점화식은 다음과 같다.
$$ a_i = \min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}) + 1 $$
단, 1을 빼는 연산을 제외하고는 해당 수로 나누어 떨어질 때에만 점화식을 사용할 수 있다.
2) 소스 코드 (Python)
# 정수 X 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위해 DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍 진행 (Buttom-up)
for i in range(2, x + 1):
# 1 빼는 경우
d[i] = d[i - 1] + 1
# 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])
i가 1일 경우에는 자기 자신이 그대로 1이기 때문에 연산을 수행할 필요가 없으므로, 0으로 초기화 한다.
3) 소스 코드 (C++)
#include <bits/stdc++.h>
using namespace std;
// 앞서 계산된 결과를 저장하기 위한 DP 테이블
int d[30001];
int x;
int main(void) {
cin >> x;
// 다이나믹 프로그래밍 진행 (Buttom-up)
for (int i = 0; i <= x; i++) {
// 1을 빼는 경우
d[i] = d[i - 1] + 1;
// 2로 나누어 떨어지는 경우
if (i % 2 == 0)
d[i] = min(d[i], d[i / 2] + 1);
// 3으로 나누어 떨어지는 경우
if (i % 3 == 0)
d[i] = min(d[i], d[i / 3] + 1);
// 5로 나누어 떨어지는 경우
if (i % 5 == 0)
d[i] = min(d[i], d[i / 5] + 1);
}
cout << d[x] << endl;
return 0;
}
로직은 완전히 똑같다.
코드의 차이점은, 파이썬의 경우 몫을 계산할 때 '//' 라는 연산을 사용해야 하지만, C++의 경우 int 자료형에서 자동으로 몫의 결과가 반환되기 때문에 나누기 연산만 수행해주면 된다.
7. 다이나믹 프로그래밍 예제 - 효율적인 화폐 구성
Q) N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용하여 그 가치의 합이 M원이 되도록 하려 한다. 이때 각 종류의 화폐는 몇개라도 사용할 수 있다고 가정한다.
예를 들어, 2원, 3원 단위의 화폐가 있을 때에는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오.
- 입력 조건
- 첫째 줄에 N, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000)
- 이후의 N개 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.
- 출력 조건
- 첫째 줄에 최소 화폐 개수를 출력한다. 불가능한 경우 -1을 출력한다.
- 입력 예시
- 2 15
- 2
- 3
- 출력 예시
- 5
1) 문제 해결 아이디어
다음과 같이 변수를 설정하고,
\(a_i\) = 금액 \(i\)를 만들 수 있는 최소한의 화폐 개수
\(k\) = 각 화폐의 단위
작은 금액부터 부분 해를 구할 수 있다.
점화식은 다음과 같다.
각 화폐 단위인 \(k\)를 하나씩 확인하며
- \(a_{i - k}\)를 만드는 방법이 존재하는 경우, \(a_i = \min(a_i, a_{i - k} + 1) \)
- \(a_{i - k}\)를 만드는 방법이 존재하지 않는 경우, \(a_i = INF \)
결과적으로 화폐 단위 개수는 총 N개이며, 그 때마다 각각의 금액에 대해 만드는 방법이 존재하는지 아닌지 판별해야 하기 때문에 N × M의 시간복잡도를 갖는다.
예를 들어, \(N = 3, M = 7\)이고, 각 화폐의 단위가 \(2, 3, 5\)인 경우를 확인해보자.
[Step 0] 초기화
먼저 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정한다.
INF는 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미를 갖는다.
본 문제에서는 M의 최댓값이 10000인데, 가장 작은 화폐 단위가 1이라 가정하면 가능한 최댓값이 10000이므로 '10001'이라는 값을 INF로 설정하면 될 것이다.
[Step 1] 첫 번째 화폐 단위 '2'
점화식에 따라 다음과 같이 리스트가 갱신됨을 알 수 있다.
만드는 방법이 존재하지 않으면 그대로 10001이라는 INF값이 주어지게 된다.
[Step 2] 두 번째 화폐 단위 '3'
$$ a_7 = \min(a_7, a_{7-3} + 1) $$
이라는 점화식을 통해 인덱스 7의 값을 구할 수 있다.
[Step 3] 세 번째 화폐 단위 '5'
같은 로직으로
$$ a_7 = \min(a_7, a_{7-5} + 1) $$
이라는 점화식에서 기존의 값인 3보다 \(a_2 + 1 \) 값이 2로 더 작으므로, 값을 갱신한다.
2) 소스 코드 (Python)
# 정수 N, M값 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보 입력받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블
d = [10001] * (n + 1)
# 다이나믹 프로그래밍 진행 (Buttom-up)
d[0] = 0
for i in range(n):
for j in range(array[i], n + 1):
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
반복문에서 i는 화폐 단위의 index, j는 각 금액의 index를 말한다.
3) 소스 코드 (C++)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> arr;
int main(void) {
cin >> n >> m;
// N개의 화폐 단위 정보를 입력받기
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
vector<int> d(m + 1, 10001); // DP 테이블 초기화
// 다이나믹 프로그래밍 진행 (Buttom-up)
d[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i]; j <= m; j++) {
if (d[j - arr[i]] != 10001) { // (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - arr[i]] + 1);
}
}
}
if (d[m] == 10001) cout << -1 << endl;
else cout << d[m] << endl;
}
로직은 똑같다. 다만, DP 테이블을 특정 값으로 초기화하는 방법을 주목하자.
최근댓글