1. 01 배낭 문제 (01 Knapsack Problem)
01 배낭 문제는 DP의 가장 기초적인 형태 중 하나입니다. 주어진 물건들이 각각 무게와 가치를 가지고 있을 때, 배낭의 용량을 초과하지 않으면서 가치의 합을 최대화하는 것이 목표입니다. 각 물건은 단 하나씩만 존재하므로 '선택한다(1)' 또는 '선택하지 않는다(0)'의 두 가지 상태만 가집니다.
일반적으로 2차원 배열로 표현할 수 있으나, 공간 복잡도를 최적화하기 위해 1차원 배열을 뒤에서부터 갱신하는 방식을 주로 사용합니다. 역순으로 순회하는 이유는 현재 물건이 중복 계산되는 것을 방지하기 위함입니다.
// C++: 01 배낭 문제 최적화 구현
for (int i = 0; i < item_count; i++) {
for (int j = max_weight; j >= weights[i]; j--) {
dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
}
}
2. 배낭 문제 (Complete Knapsack Problem)
01 배낭 문제와 달리 각 물건의 개수가 무한대인 경우입니다. 동일한 물건을 여러 번 선택할 수 있기 때문에, 상태 전이 시 현재 물건을 다시 고려할 수 있도록 순방향으로 루프를 돌립니다.
// C++: 완전 배낭 문제 구현
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int total_capacity, n;
std::cin >> total_capacity >> n;
std::vector<long long> dp(total_capacity + 1, 0);
for (int i = 0; i < n; i++) {
int w, v;
std::cin >> w >> v;
for (int j = w; j <= total_capacity; j++) {
dp[j] = std::max(dp[j], dp[j - w] + v);
}
}
std::cout <> dp[total_capacity];
return 0;
}
3. 구간 DP (Interval DP)
구간 DP는 특정 구간 $[i, j]$에 대한 최적해를 구하기 위해 해당 구간을 더 작은 구간들로 나누어 해결하는 방식입니다. 대표적으로 행렬 곱셈 순서 문제나 돌 합치기 문제가 있습니다. 보통 구간의 길이를 1부터 늘려가며 계산합니다.
// C++: 구간 DP의 일반적인 구조
for (int len = 2; len <= n; len++) { // 구간의 길이
for (int i = 1; i <= n - len + 1; i++) { // 시작점
int j = i + len - 1; // 끝점
dp[i][j] = INF;
for (int k = i; k < j; k++) { // 분할 지점
dp[i][j] = std::min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j));
}
}
}
4. 상태 압축 DP (State Compression DP)
상태 압축 DP는 문제에서 다루는 상태의 수가 적을 때, 비트마스크 등을 이용해 상태를 정수로 표현하여 메모리를 절약하는 기법입니다. 하지만 넓은 의미에서는 불필요한 차원을 제거하거나 변환하여 효율성을 높이는 기법을 포함합니다.
예를 들어, 여러 수의 곱에서 끝자리에 오는 0의 개수를 최대화하는 문제는 2와 5의 인수의 개수를 관리하는 DP로 변환할 수 있습니다. 2의 개수와 5의 개수 중 작은 값이 0의 개수가 되므로, 하나를 상태(인덱스)로 두고 다른 하나를 DP 테이블의 값으로 저장하여 최적화합니다.
// C++: 인수 분해를 활용한 상태 최적화 DP
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
long long dp[201][6501]; // 선택한 개수, 5의 인수 합
int main() {
int n, k;
std::cin >> n >> k;
std::memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
long long val;
std::cin >> val;
int c2 = 0, c5 = 0;
while (val > 0 && val % 2 == 0) { c2++; val /= 2; }
while (val > 0 && val % 5 == 0) { c5++; val /= 5; }
for (int j = k; j >= 1; j--) {
for (int s = 6500; s >= c5; s--) {
if (dp[j - 1][s - c5] != -1)
dp[j][s] = std::max(dp[j][s], dp[j - 1][s - c5] + c2);
}
}
}
long long max_zeros = 0;
for (int s = 0; s <= 6500; s++) {
max_zeros = std::max(max_zeros, std::min((long long)s, dp[k][s]));
}
std::cout << max_zeros;
return 0;
}
5. 트리 DP (Tree DP)
트리 구조 위에서 정의되는 DP로, 보통 서브트리의 정보를 기반으로 부모 노드의 값을 결정합니다. DFS(깊이 우선 탐색)를 통해 리프 노드부터 루트 노드까지 상향식으로 값을 계산해 나갑니다.
대표적인 예로 '트리의 독립 집합(Independent Set)' 문제가 있습니다. 특정 노드를 포함할 때와 포함하지 않을 때의 최적값을 각각 나누어 저장합니다.
// C++: 트리 DP (최대 독립 집합 형태)
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> tree[6001];
int happiness[6001];
int cache[6001][2];
void solve(int u) {
cache[u][1] = happiness[u];
cache[u][0] = 0;
for (int v : tree[u]) {
solve(v);
// 내가 참여하지 않으면 부모는 참여하거나 참여하지 않을 수 있음
cache[u][0] += std::max(cache[v][0], cache[v][1]);
// 내가 참여하면 부모는 반드시 참여하지 않아야 함
cache[u][1] += cache[v][0];
}
}
int main() {
int n;
std::cin >> n;
for (int i = 1; i <= n; i++) std::cin >> happiness[i];
// 트리 구조 및 루트 노드 판별 로직 생략
// solve(root);
// std::cout << std::max(cache[root][0], cache[root][1]);
return 0;
}