이 DP 아님
🌟DP
Dynamic Programming
동적 계획법
문제를 작은 문제들로 쪼개어 이전에 구해놨던 값을 현재의 풀이에 활용할 수 있을 때 이를 동적계획법이라고 함.
📌응용 예시
- 경우의 수(동전들로 금액 만드는 모든 경우의 수) 조합, 순열
- 모든 경우로부터 최대 최소(가장 적은 동전으로 금액 만들기, LIS(O^N), 냅색 문제)
- 수열 문제(피보나치, 카탈린.. 수열의 응용도 결국 경우의 수로 들어가지만)
📌구현 방식
1. Bottom-up (for문 구현)
현재 상태 값의 갱신을 위해, 현재 상태가 될 수 있는 이전 상태들의 값을 본다.
바텀업으로 값을 채워주는 것을 Tabulation 이라고 함
2. Top-down (재귀함수 구현)
현재 상태 값의 갱신을 위해, 현재 상태로부터 될 수 있는 다음 상태들의 값을 본다.
(재귀 함수이므로, Base condition에 도달하게 되면 값을 가지고 다시 현재상태로 온다.)
탑다운으로 값을 채워주는 것을 Memoization 이라고 함.
메모이제이션 된 값은 항상 같은 값을 반환해야 한다.
바텀업이든 탑다운이든, 초기값을 잘 설정해주는 것이 중요하다.
또한, 탑다운 방식의 경우, 그냥 dfs와 달리 값을 메모이제이션 하는 것에 의미가 있다.
그래서 이미 값을 계산하였다면 더 이상 재귀호출을 하지 말고 이미 계산한 값을 반환하도록 하는 것이 중요하다.
정직한 동전 사진
🌟동전 문제풀이 방식
📌기본 아이디어
매 금액마다 이전에 만든 금액에 동전을 얹어준다.
→ 이는 현재 금액을 만드는 경우의 수에, (이전에 만든 금액 - 현재 동전)의 경우의 수가 포함됨을 의미함.
대부분 2중 for문으로 구현된다.
📌중복 순열
중복 순열 문제의 경우, 동전을 사용할 때 순서가 고려된다.
ex) 1+2+1 과 1+1+2 를 다른 경우의 수로 본다
💡 만드려는 금액을 바깥쪽 루프에 두고, 사용하는 동전을 안쪽 루프에 둔다.
매 금액마다 모든 동전을 사용하여 만드는 경우의 수를 확인한다. 다음 금액에서는 이전 금액에서 모든 동전을 사용하여 만드는 경우의 수에 새로운 동전을 얹는데, 이때 순서도 고려된다.
1, 2, 3 동전으로 1, 2, 3 금액 만들기
| 동전/금액 | 1원 | 2원 | 3원 |
|---|---|---|---|
| 동전 1 | 1 | 1+1 | 1+1+1, 2+1 |
| 동전 2 | 2 | 1+2 | |
| 동전 3 | 3 |
매 금액마다 모든 동전에 대해서 해당 금액을 만드는 방법을 확인해보았다.
3이라는 금액을 만드는 경우를 보자.
1원에 2원짜리 동전 얹어 1+2 만들기
2원에 1원짜리 동전 얹어 1+1+1과 2+1 만들기
0원에 3원짜리 동전 얹어 3 만들기
1+2와 2+1은 사용하는 동전의 종류와 갯수가 같지만, 순서가 다르다.
이처럼 순열에 대해 따져보려면, 금액을 바깥에, 동전을 안쪽에 두고 경우를 따져본다.
// 중복 순열
for(int i = 1; i <= MX; i++) { // 만드는 금액
for(int j = 0; j < N; j++) { // 사용하는 동전 인덱스
if(i >= a[j]) dp[i] += dp[i - a[j]];
}
} 📌중복 조합
조합은 순열과 다르게 순서를 따지지 않는다. 중복 조합은 동전의 중복 사용을 허용하지만, 순서가 다르고 사용하는 동전의 종류와 갯수가 같으면 같은 조합으로 본다.
💡 사용하는 동전 루프를 바깥쪽에 두고, 만드려는 금액 루프를 안쪽에 둔다.
어떤 금액을 만들 때 한 종류의 동전만 연속해서 얹어서 만들수 있는 금액을 생각한다. 한 종류 동전으로 만들 수 있는 금액이 모두 만들어지면, 다음 종류의 동전을 사용해 반복한다. 기본 아이디어는 이전 금액에 새로운 동전을 얹는 것으로 같지만, 한 종류의 동전만 얹어주기 때문에 순서가 고려되지 않는다.
1, 2, 3 동전으로 1, 2, 3 금액 만들기
| 동전/금액 | 1원 | 2원 | 3원 |
|---|---|---|---|
| 동전 1 | 1 | 1+1 | 1+1+1 |
| 동전 2 | 2 | 1+2 | |
| 동전 3 | 3 |
3이라는 금액에서,
1+1+1은 현재 종류의 동전이 1일때, 금액 2에 동전 1을 얹는 것과 같고
1+2는 현재 종류의 동전이 2일때, 금액 1에 동전 2를 얹는 것과 같다.
한 종류의 동전을 계속 얹어서 금액을 만드는 방법을 확인해보았다.
금액에서 서로 다른 동전이 여러번 끼어들지 않고, 현재 종류의 동전만이 얹어지기 때문에, 순서는 고려되지 않고, 조합이 만들어진다.
// 중복 조합
for(int i = 0; i < N; i++) { // 사용하는 동전 인덱스
for(int j = a[i]; j<= MX; j++) { // 만드는 금액
dp[j] += dp[j-a[i]];
}
}📌중복을 허용하지 않는 조합
여태까지는 중복을 허용한 순열과 조합을 확인해보았다.
금액을 만들 때 동전을 종류별로 최대 하나씩만 사용할 수 있다면 어떨까
(현재 금액 - 현재 동전)을 만드는 경우의 수를 알아야 하는 것은 같지만, 그 금액을 만들 때 사용했던 동전들은 현재 동전 이전의 동전까지만 포함되어야 한다.
조합 문제에서 동전은 바깥, 금액은 안쪽이다.
동전 인덱스를 i, 금액을 j라고 하자.
만들어야 하는 금액 ⇒ j - a[i]
그 금액을 만드는데 사용될 수 있는 최대 동전 인덱스 ⇒ i-1
1. 중복 조합 - 2차원 배열 풀이
dp[j][i] => j는 금액, i는 동전 인덱스
- i번 동전을 사용하지 않고 금액 j를 만드는 경우
=> dp[j][i-1]
이는 i-1번까지의 동전을 사용해서 금액 j를 만드는 경우와 같다 - i번 동전을 사용하고 금액 j를 만드는 경우
=> dp[j-a[i]][i-1]
i-1번까지의 동전을 사용해서 금액 j-a[i]를 만드는 경우와 같다(그 위에 i번 동전을 얹음)
for(int i = 0; i < N; i++) { // 사용하는 동전 인덱스
for(int j = 1; j <= MX; j++) { // 만드는 금액
dp[j][i] = dp[j][i - 1]; // i번 동전을 사용하지 않는 경우
if(j >= a[i]) dp[j][i] += dp[j - a[i]][i - 1]; // i번 동전도 사용하는 경우
}
}2. 중복 조합 - 1차원 배열 풀이
1차원 dp로도 중복을 허용하지 않는 조합 문제를 풀 수 있다.
역시 조합 문제에서는 바깥쪽이 동전, 안쪽이 금액임에는 변함없다.
금액을 오름차순으로 순회, 갱신 시,
현재 동전으로 이전 금액을 만드는 경우까지 포함이 되므로, 현재 동전이 여러번 쓰이게 된다.
금액을 내림차순으로 순회, 갱신 시,
현재 동전으로 이전 금액을 만드는 경우는 포함되지 않고, 이전 동전으로 이전 금액을 만드는 경우까지만 포함이 되어 현재 동전은 최대 한 번만 쓰인다.
💡 중복이 허용되지 않는 조합에서 1차원 배열을 사용하는 경우 금액 내림차순으로 경우의 수를 따진다
// 중복이 허용되지 않는 조합
for(int i = 0; i < n; i++) { // 사용하는 동전 인덱스
for(int j = MX; j >= a[i]; j--) { // 만드는 금액
dp[j] += dp[j - a[i]];
}
}📌제한된 갯수에서 중복을 허용하는 조합
1. 제한된 갯수에서 중복허용 - 2차원 배열 풀이
#include <iostream>
#include <vector>
#define X first
#define Y second
using namespace std;
int T, K, dp[10005][105]; // => 조합 수 of (금액, 사용한 동전 최대 인덱스)
vector<pair<int, int>> v;
int main(void) {
ios::sync_with_stdio(0), cin.tie(0);
cin >> T >> K;
v.resize(K + 1);
// X = 동전 금액, Y = 해당 동전 개수
for (int i = 1; i <= K; i++) cin >> v[i].X >> v[i].Y;
for (int i = 1; i <= K; i++) {
dp[0][i - 1] = 1;
for (int k = 1; k <= v[i].Y; k++) {
for (int j = v[i].X * k; j <= T; j++) {
dp[j][i] += dp[j - v[i].X * k][i - 1];
// i번째 동전을 사용하는 경우
// 2차원 배열로 되어있기 때문에, i-1번째 동전까지 사용한 경우를 따져주므로,
// 현재 동전이 의도치 않게 중복 계산 되는 경우는 배제됨
}
}
for (int j = 1; j <= T; j++) dp[j][i] += dp[j][i - 1];
// i번째 동전을 사용하지 않는 경우
}
cout << dp[T][K];
}동전 바깥, 금액 안쪽
2차원 dp 방법의 경우 메모리 사용량은 커지지만
동전의 갯수를 바깥에 두기 때문에(동전의 갯수를 안쪽에 두더라도 같은 결과를 내지만 시간 단축 x), 동전의 갯수 * 동전금액 보다 금액이 커질 때부터 순회한다.
⇒ 시간복잡도는 줄어든다.
2. 제한된 갯수에서 중복을 허용 - 1차원 배열 풀이
#include <iostream>
using namespace std;
int T, K, dp[10005];
vector<pair<int, int>> v;
int main(void) {
ios::sync_with_stdio(0), cin.tie(0);
cin >> T >> K;
v.resize(K + 1);
// X = 동전 금액, Y = 해당 동전 개수
for (int i = 1; i <= K; i++) cin >> v[i].X >> v[i].Y;
dp[0] = 1;
for (int i = 1; i <= K; i++) {
for (int j = T; j >= 1; j--) { // 금액 내림차
for (int k = 1; k <= v[i].Y; k++) {
if(j >= k * v[i].X) dp[j] += dp[j - k * v[i].X];
}
}
}
cout << dp[T];
}금액 바깥 동전 안쪽
1차원 배열 방법의 경우, 메모리 사용량은 줄어들지만
각 금액마다 해당 동전의 갯수만큼 for문을 돌게되어, 시간 복잡도는 늘어난다.
현재 종류 동전에서 계산된 이전 금액 조합이 현재 종류 동전의 다음 금액 조합에 반영되면 안 되기 때문에, (더 큰 금액에서의 조합에는 이전 종류 동전까지의 조합만 반영되어야 한다.) 1차원 dp로 계산할 때는 금액을 내림차순으로 순회하며 갱신한다.
1차원 배열에서 동전갯수 for문(인덱스 k의)을 금액 for문의 바깥쪽에 두게 되면, 현재 동전이 의도치 않게 중복 계산되게 된다. (⇒ 제한한 v[i].Y의 갯수가 아닌 더 많은 갯수의 현재 동전에 대한 조합을 계산하게 된다.)
고로 제한된 갯수에서 중복을 허용하는 1차원 배열 풀이에서는 금액이 바깥에서 내림차순으로 순회하고, 동전은 안쪽에서 순회한다.
'알고리즘' 카테고리의 다른 글
| 포인터, alias 개념과 직접 구현 해시 (0) | 2024.08.20 |
|---|---|
| 외판원 순회(TSP) 알고리즘 (0) | 2024.08.20 |
