다이나믹 프로그래밍(DP)은 다음 두 가지 특성을 만족하는 문제에 적용할 수 있습니다:
1. 중복되는 하위 문제 (Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 등장합니다.
2. 최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 하위 문제의 최적 해결 방법으로부터 구성될 수 있습니다.
DP는 이러한 특성을 이용하여 하위 문제의 결과를 저장하고, 이를 재사용함으로써 전체 문제를 효율적으로 해결합니다.
DP의 접근 방식
• 메모이제이션 (Memoization): 재귀적으로 문제를 해결하면서, 이미 계산된 결과를 저장하여 다시 계산하지 않도록 하는 방법입니다.
• 타뷸레이션 (Tabulation): 작은 하위 문제부터 순차적으로 해결해가며, 그 결과를 테이블에 저장하는 방법입니다.
예시: 피보나치 수열
피보나치 수열은 DP의 기본적인 예시입니다. 피보나치 수열의 n번째 항은 (n-1)번째 항과 (n-2)번째 항의 합으로 정의됩니다.
피보나치 수열의 재귀적 접근과 시간 복잡도
피보나치 수열을 단순한 재귀적으로 계산하는 방법은 이해하기 쉽지만, 중복 계산이 많아 비효율적입니다.
#include <iostream>
using namespace std;
// 피보나치 수를 재귀적으로 계산하는 함수
long long fibonacci_recursive(int n) {
if (n <= 1)
return n;
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}
int main() {
int n = 40;
cout << "피보나치(" << n << ") = " << fibonacci_recursive(n) << endl;
return 0;
}시간 복잡도: O(2^n)
문제점: 중복된 계산이 많아 n이 커질수록 매우 비효율적입니다.
다이나믹 프로그래밍 (메모이제이션)과 시간 복잡도
메모이제이션을 사용하면 중복 계산을 피할 수 있어 효율성이 크게 향상됩니다.
#include <iostream>
#include <vector>
using namespace std;
// 피보나치 수를 메모이제이션을 사용하여 계산하는 함수
long long fibonacci_dp(int n, vector<long long> &memo) {
if (n <= 1)
return n;
// 이미 계산된 값이 있으면 반환
if (memo[n] != -1)
return memo[n];
// 계산되지 않았다면 계산 후 저장
memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo);
return memo[n];
}
int main() {
int n = 40;
// 메모이제이션을 위한 벡터 초기화 (-1로 초기화)
vector<long long> memo(n + 1, -1);
cout << "피보나치(" << n << ") = " << fibonacci_dp(n, memo) << endl;
return 0;
}시간 복잡도: O(n)
장점: 중복 계산을 피하여 효율성이 크게 향상됩니다.
2. 이항 계수 (Binomial Coefficient) - 분할 정복과 다이나믹 프로그래밍
개요
이항 계수는 조합을 계산하는 방법으로, “n개 중에서 k개를 선택하는 경우의 수”를 의미합니다.
분할 정복 접근 (재귀)과 시간 복잡도
재귀적으로 이항 계수를 계산하면 중복 계산이 발생하여 비효율적입니다.
#include <iostream>
using namespace std;
// 이항 계수를 재귀적으로 계산하는 함수
long long binomial_recursive(int n, int k) {
// 기본 조건
if (k == 0 || k == n)
return 1;
// 재귀적으로 계산
return binomial_recursive(n - 1, k - 1) + binomial_recursive(n - 1, k);
}
int main() {
int n = 5, k = 2;
cout << "C(" << n << ", " << k << ") = " << binomial_recursive(n, k) << endl;
return 0;
}시간 복잡도: O(2^n)
문제점: 중복 계산이 많아 큰 n과 k에 대해 비효율적입니다.
다이나믹 프로그래밍 접근과 시간 복잡도
DP를 사용하면 중복 계산을 피할 수 있어 효율성이 크게 향상됩니다.
#include <iostream>
#include <vector>
using namespace std;
// 이항 계수를 다이나믹 프로그래밍으로 계산하는 함수
long long binomial_dp(int n, int k) {
// 이항 계수를 저장할 2D 벡터 생성
vector<vector<long long>> C(n + 1, vector<long long>(k + 1, 0));
// 모든 C(n, 0)과 C(n, n)은 1
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
if (i <= k)
C[i][i] = 1;
}
// 다이나믹 프로그래밍을 이용하여 이항 계수 계산
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i && j <= k; j++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return C[n][k];
}
int main() {
int n = 5, k = 2;
cout << "C(" << n << ", " << k << ") = " << binomial_dp(n, k) << endl;
return 0;
}시간 복잡도: O(nk)
장점: 중복 계산을 피하여 효율성이 크게 향상됩니다.
3. Floyd의 최단 경로 알고리즘 (Floyd-Warshall Algorithm)
개요
Floyd-Warshall 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다이나믹 프로그래밍을 기반으로 하며, 음수 간선이 존재하더라도 음수 사이클이 없어야 정상적으로 동작합니다.
알고리즘 설명
1. 초기화: 각 정점 간의 거리를 직접 연결된 간선의 가중치로 초기화합니다. 연결되지 않은 정점은 무한대로 설정합니다.
2. 점화식: 중간 정점을 하나씩 추가하며, 각 정점 쌍 사이의 최단 거리를 업데이트합니다.
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
여기서 k는 중간 정점입니다.
C++ 구현과 시간 복잡도
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9; // 무한대를 나타내는 값
// Floyd-Warshall 알고리즘을 사용하여 모든 정점 간의 최단 경로를 계산
void floyd_warshall(vector<vector<int>> &dist, int V) {
// 점화식을 적용하여 최단 거리 업데이트
for (int k = 0; k < V; k++) { // 중간 정점
for (int i = 0; i < V; i++) { // 출발 정점
for (int j = 0; j < V; j++) { // 도착 정점
// i에서 j로 가는 경로를 i -> k -> j로 업데이트할 수 있는지 확인
if (dist[i][k] != INF && dist[k][j] != INF)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main() {
int V = 4; // 정점의 수
// 인접 행렬 초기화 (INF는 연결되지 않음을 의미)
vector<vector<int>> dist = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floyd_warshall(dist, V);
// 모든 정점 간의 최단 거리 출력
cout << "모든 정점 간의 최단 거리:" << endl;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
return 0;
}시간 복잡도: O(V³)
설명:
• V는 정점의 수입니다.
• 세 개의 중첩된 반복문을 사용하여 모든 정점 쌍에 대해 최단 거리를 계산합니다.
• 매우 효율적이지만, 정점의 수가 매우 클 경우 비효율적일 수 있습니다.
모든 정점 간의 최단 거리:
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 04. 다이나믹 프로그래밍과 최적화 문제 - 배낭 문제 (Knapsack Problem)
개요
배낭 문제는 주어진 무게와 가치를 가진 물건들 중에서, 무게의 제한을 넘지 않으면서 최대의 가치를 가지도록 물건을 선택하는 문제입니다. DP는 이 문제를 효율적으로 해결할 수 있는 방법을 제공합니다.
0-1 배낭 문제
각 물건을 하나씩만 선택할 수 있는 배낭 문제입니다.
알고리즘 설명과 시간 복잡도
DP 테이블을 사용하여 각 아이템과 무게 제한에 대해 최적의 가치를 계산합니다.
시간 복잡도: O(nW)
• n은 아이템의 수
• W는 배낭의 무게 제한
C++ 구현
#include <iostream>
#include <vector>
using namespace std;
// 0-1 배낭 문제를 다이나믹 프로그래밍으로 해결
int knapsack(int W, const vector<int> &weights, const vector<int> &values, int n) {
// DP 테이블 초기화: (n+1) x (W+1) 크기의 2D 벡터
// dp[i][w]는 처음 i개의 아이템으로 무게 w를 채울 때의 최대 가치
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// 각 아이템을 하나씩 고려
for (int i = 1; i <= n; i++) {
// 각 무게에 대해 최대 가치를 계산
for (int w = 0; w <= W; w++) {
if (weights[i - 1] <= w) {
// 현재 아이템을 선택한 경우와 선택하지 않은 경우 중 최대값 선택
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
}
else {
// 현재 아이템을 선택할 수 없는 경우 이전 아이템의 값 유지
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W]; // 최대 가치 반환
}
int main() {
int W = 50; // 배낭의 무게 제한
vector<int> weights = {10, 20, 30}; // 물건들의 무게
vector<int> values = {60, 100, 120}; // 물건들의 가치
int n = weights.size();
cout << "최대 가치: " << knapsack(W, weights, values, n) << endl;
return 0;
}출력:
최대 가치: 220설명:
• dp[i][w]는 처음 i개의 아이템으로 무게 w를 채울 때의 최대 가치를 저장합니다.
• 각 아이템을 선택할지 말지를 결정하면서, 선택한 경우와 선택하지 않은 경우 중 최대값을 선택합니다.
• 최종적으로 dp[n][W]에는 전체 아이템을 고려했을 때 무게 제한 W 내에서의 최대 가치가 저장됩니다.
공간 복잡도 최적화
위의 구현은 O(nW)의 공간을 사용합니다. 그러나 이 문제는 이전 상태만 필요하므로, 공간을 O(W)로 줄일 수 있습니다.
#include <iostream>
#include <vector>
using namespace std;
// 0-1 배낭 문제를 다이나믹 프로그래밍으로 해결 (공간 최적화)
int knapsack_space_optimized(int W, const vector<int> &weights, const vector<int> &values, int n) {
// DP 테이블 초기화: 1D 벡터
// dp[w]는 무게 w를 채울 때의 최대 가치
vector<int> dp(W + 1, 0);
// 각 아이템을 하나씩 고려
for (int i = 0; i < n; i++) {
// 무게 제한을 뒤에서부터 업데이트
for (int w = W; w >= weights[i]; w--) {
dp[w] = max(dp[w], values[i] + dp[w - weights[i]]);
}
}
return dp[W]; // 최대 가치 반환
}
int main() {
int W = 50; // 배낭의 무게 제한
vector<int> weights = {10, 20, 30}; // 물건들의 무게
vector<int> values = {60, 100, 120}; // 물건들의 가치
int n = weights.size();
cout << "최대 가치 (공간 최적화): " << knapsack_space_optimized(W, weights, values, n) << endl;
return 0;
}출력:
최대 가치 (공간 최적화): 220설명:
• 2D DP 테이블 대신 1D DP 테이블을 사용하여 공간을 절약합니다.
• 아이템을 선택할 때마다 무게 제한을 뒤에서부터 업데이트하여 중복 계산을 피합니다.
5. 연쇄 행렬 곱셈 (Chained Matrix Multiplication)
개요
연쇄 행렬 곱셈 문제는 여러 개의 행렬을 곱할 때, 곱셈 순서를 최적화하여 곱셈 연산의 수를 최소화하는 문제입니다. 행렬 곱셈의 연산 수는 행렬의 차원에 따라 달라지므로, 적절한 순서를 선택하는 것이 중요합니다.
알고리즘 설명과 시간 복잡도
DP를 사용하여, 모든 가능한 행렬 곱셈 순서를 고려하면서 최소 연산 수를 계산합니다.
시간 복잡도: O(n³)
• n은 행렬의 개수
C++ 구현
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 연쇄 행렬 곱셈의 최소 연산 수를 다이나믹 프로그래밍으로 계산
int matrixChainMultiplication(const vector<int> &p, int n) {
// DP 테이블 초기화: n x n 크기의 2D 벡터
// dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱할 때의 최소 연산 수
vector<vector<int>> dp(n, vector<int>(n, 0));
// L은 곱셈 범위의 길이
for (int L = 2; L < n; L++) { // L=2부터 n-1까지
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
// 비용 계산: dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
int cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost < dp[i][j])
dp[i][j] = cost;
}
}
}
return dp[1][n - 1]; // 전체 행렬의 최소 연산 수 반환
}
int main() {
// 행렬의 차원 배열 (예: A1: 10x30, A2: 30x5, A3: 5x60)
vector<int> p = {10, 30, 5, 60};
int n = p.size();
cout << "최소 연산 수: " << matrixChainMultiplication(p, n) << endl;
return 0;
}출력:
최소 연산 수: 4500설명:
• p는 행렬의 차원을 나타내는 배열입니다. 예를 들어, p = {10, 30, 5, 60}는 A1: 10x30, A2: 30x5, A3: 5x60을 의미합니다.
• dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱할 때의 최소 연산 수를 저장합니다.
• 각 범위의 길이를 증가시키면서, 가능한 모든 분할 지점 k를 고려하여 최소 연산 수를 계산합니다.
• 최종적으로 dp[1][n-1]에는 전체 행렬을 곱할 때의 최소 연산 수가 저장됩니다.
시간 복잡도 분석
• 외부 루프: L은 2부터 n-1까지, O(n)
• 두 번째 루프: i는 1부터 n-L까지, O(n)
• 내부 루프: k는 i부터 j-1까지, O(n)
• 따라서 전체 시간 복잡도는 O(n³)입니다.
6. 최적 이진 탐색 트리 (Optimal Binary Search Trees)
개요
최적 이진 탐색 트리 문제는 주어진 키들의 검색 확률을 고려하여 이진 탐색 트리를 구성할 때, 전체 검색 비용이 최소가 되도록 트리를 구성하는 문제입니다.
알고리즘 설명과 시간 복잡도
DP를 사용하여, 모든 가능한 키의 범위에 대해 최적의 트리를 구성합니다. 각 서브트리에 대해 최적의 루트를 선택하면서 전체 비용을 최소화합니다.
시간 복잡도: O(n³)
• n은 키의 수
C++ 구현
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 최적 이진 탐색 트리의 최소 검색 비용을 다이나믹 프로그래밍으로 계산
int optimalBST(const vector<int> &keys, const vector<int> &freq, int n) {
// DP 테이블 초기화: n x n 크기의 2D 벡터
// dp[i][j]는 keys[i]부터 keys[j]까지의 최소 검색 비용
vector<vector<int>> dp(n, vector<int>(n, 0));
// 간격(interval) 별로 계산
for (int len = 1; len <= n; len++) { // 서브트리의 길이
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
// 루트를 k로 선택
for (int k = i; k <= j; k++) {
// 왼쪽 서브트리와 오른쪽 서브트리의 비용 계산
int cost = 0;
if (k > i)
cost += dp[i][k - 1];
if (k < j)
cost += dp[k + 1][j];
// 현재 범위의 빈도 합 계산
int sum_freq = 0;
for (int m = i; m <= j; m++)
sum_freq += freq[m];
cost += sum_freq;
if (cost < dp[i][j])
dp[i][j] = cost;
}
}
}
return dp[0][n - 1]; // 전체 키의 최소 검색 비용 반환
}
int main() {
// 키들과 각 키의 검색 빈도
vector<int> keys = {10, 12, 20};
vector<int> freq = {34, 8, 50};
int n = keys.size();
cout << "최소 검색 비용: " << optimalBST(keys, freq, n) << endl;
return 0;
}출력:
최소 검색 비용: 142설명:
• keys는 이진 탐색 트리의 키들을 오름차순으로 정렬한 배열입니다.
• freq는 각 키의 검색 빈도를 나타내는 배열입니다.
• dp[i][j]는 keys[i]부터 keys[j]까지의 키들로 구성된 서브트리의 최소 검색 비용을 저장합니다.
• 각 서브트리의 루트를 선택할 때, 왼쪽과 오른쪽 서브트리의 비용과 현재 범위의 빈도 합을 더하여 최소 비용을 선택합니다.
• 최종적으로 dp[0][n-1]에는 전체 키를 포함하는 트리의 최소 검색 비용이 저장됩니다.
시간 복잡도 분석
• 외부 루프: len는 1부터 n까지, O(n)
• 두 번째 루프: i는 0부터 n-len까지, O(n)
• 내부 루프: k는 i부터 j까지, O(n)
• 추가로, 빈도 합을 계산하기 위해 O(n)이 소요되므로 전체 시간 복잡도는 O(n⁴)
개선: 빈도 합을 미리 계산해두면 시간 복잡도를 O(n³)으로 줄일 수 있습니다.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 최적 이진 탐색 트리의 최소 검색 비용을 다이나믹 프로그래밍으로 계산 (빈도 합 사전 계산)
int optimalBST_optimized(const vector<int> &keys, const vector<int> &freq, int n) {
// DP 테이블 초기화: n x n 크기의 2D 벡터
// dp[i][j]는 keys[i]부터 keys[j]까지의 최소 검색 비용
vector<vector<int>> dp(n, vector<int>(n, 0));
// 사전 합 계산
vector<vector<int>> sum_freq(n, vector<int>(n, 0));
for(int i=0;i<n;i++) {
sum_freq[i][i] = freq[i];
for(int j=i+1;j<n;j++) {
sum_freq[i][j] = sum_freq[i][j-1] + freq[j];
}
}
// 간격(interval) 별로 계산
for (int len = 1; len <= n; len++) { // 서브트리의 길이
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
// 루트를 k로 선택
for (int k = i; k <= j; k++) {
// 왼쪽 서브트리와 오른쪽 서브트리의 비용 계산
int cost = 0;
if (k > i)
cost += dp[i][k - 1];
if (k < j)
cost += dp[k + 1][j];
// 현재 범위의 빈도 합을 미리 계산된 값 사용
cost += sum_freq[i][j];
if (cost < dp[i][j])
dp[i][j] = cost;
}
}
}
return dp[0][n - 1]; // 전체 키의 최소 검색 비용 반환
}
int main() {
// 키들과 각 키의 검색 빈도
vector<int> keys = {10, 12, 20};
vector<int> freq = {34, 8, 50};
int n = keys.size();
cout << "최소 검색 비용 (최적화): " << optimalBST_optimized(keys, freq, n) << endl;
return 0;
}출력:
최소 검색 비용 (최적화): 142설명:
• sum_freq[i][j]는 keys[i]부터 keys[j]까지의 빈도 합을 미리 계산하여 저장합니다.
• 이를 통해 빈도 합 계산을 O(1)로 줄여 전체 시간 복잡도를 O(n³)으로 줄일 수 있습니다.
7. 외판원 문제 (Traveling Salesperson Problem, TSP)
개요
외판원 문제는 주어진 모든 도시를 정확히 한 번씩 방문하고, 다시 출발지로 돌아오는 최소 비용의 경로를 찾는 문제입니다. TSP는 NP-완전 문제로, 입력 크기가 커지면 해결이 매우 어렵습니다. 하지만, 다이나믹 프로그래밍을 사용하여 효율적으로 해결할 수 있는 경우도 있습니다.
알고리즘 설명과 시간 복잡도
비트 마스킹과 메모이제이션을 결합한 다이나믹 프로그래밍 접근을 사용합니다. 상태는 현재 도시와 방문한 도시들의 집합으로 표현됩니다.
시간 복잡도: O(n² * 2^n)
• n은 도시의 수
C++ 구현
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int n; // 도시의 수
vector<vector<int>> dist_matrix; // 도시 간의 거리 행렬
vector<vector<int>> memo; // 메모이제이션 테이블
// 모든 도시를 방문했는지 확인
bool all_visited(int mask) {
return mask == ((1 << n) - 1);
}
// 외판원 문제를 해결하는 재귀 함수
int tsp(int pos, int mask) {
// 모든 도시를 방문했으면 시작 도시로 돌아감
if (all_visited(mask))
return dist_matrix[pos][0];
// 이미 계산된 경우 반환
if (memo[pos][mask] != -1)
return memo[pos][mask];
int ans = INT_MAX;
// 모든 도시를 시도
for (int city = 0; city < n; city++) {
// 아직 방문하지 않은 도시인 경우
if (!(mask & (1 << city))) {
// 다음 도시를 방문하는 비용 계산
int new_cost = dist_matrix[pos][city] + tsp(city, mask | (1 << city));
ans = min(ans, new_cost);
}
}
return memo[pos][mask] = ans;
}
int main() {
// 예제: 4개의 도시
n = 4;
dist_matrix = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
// 메모이제이션 테이블 초기화 (-1로 초기화)
memo = vector<vector<int>>(n, vector<int>((1 << n), -1));
// 외판원 문제 해결 (시작 도시는 0)
int result = tsp(0, 1 << 0);
cout << "최소 경로 비용: " << result << endl;
return 0;
}출력:
최소 경로 비용: 80설명:
• dist_matrix는 도시 간의 거리 행렬을 나타냅니다. dist_matrix[i][j]는 도시 i에서 도시 j로 가는 거리입니다.
• tsp(pos, mask) 함수는 현재 위치 pos와 방문한 도시들을 나타내는 비트마스크 mask를 인자로 받아, 남은 도시들을 방문하는 최소 비용을 반환합니다.
• memo 테이블은 이미 계산된 상태의 결과를 저장하여 중복 계산을 방지합니다.
• 시작 도시는 0번 도시로 설정하고, mask는 시작 도시에 해당하는 비트만 1로 설정하여 호출합니다.
• 최종적으로 모든 도시를 방문하고 다시 시작 도시로 돌아오는 최소 경로 비용을 출력합니다.
메모이제이션 테이블의 크기
• memo 테이블의 크기는 n x 2^n입니다.
• 각 도시마다 모든 가능한 방문 상태를 저장하므로, 메모리 사용량이 매우 커질 수 있습니다.
8. 시퀀스 정렬 (Sequence Alignment)
개요
시퀀스 정렬은 두 개의 시퀀스를 비교하여, 유사성을 최대화하거나 차이를 최소화하는 정렬 방법을 찾는 문제입니다. 주로 생물학에서 DNA, RNA, 단백질 서열의 비교에 사용됩니다. DP는 최적의 정렬을 찾는 데 효과적으로 사용됩니다.
알고리즘 설명과 시간 복잡도
동적 프로그래밍을 이용하여 두 시퀀스의 각 위치까지의 최적 정렬 비용을 계산합니다. 일반적으로 삽입, 삭제, 교체 연산에 비용을 할당하여 최적의 정렬을 찾습니다.
시간 복잡도: O(mn)
• m과 n은 두 시퀀스의 길이
C++ 구현
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 시퀀스 정렬을 다이나믹 프로그래밍으로 해결
int sequenceAlignment(const string &s1, const string &s2, int insert_cost, int delete_cost, int replace_cost) {
int m = s1.length();
int n = s2.length();
// DP 테이블 초기화: (m+1) x (n+1) 크기의 2D 벡터
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 초기 조건: 한 시퀀스를 빈 시퀀스로 만드는 비용
for (int i = 0; i <= m; i++)
dp[i][0] = i * delete_cost;
for (int j = 0; j <= n; j++)
dp[0][j] = j * insert_cost;
// DP 테이블 채우기
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
// 문자가 같으면 비용이 추가되지 않음
dp[i][j] = dp[i - 1][j - 1];
}
else {
// 삽입, 삭제, 교체 중 최소 비용 선택
dp[i][j] = min({
dp[i][j - 1] + insert_cost, // 삽입
dp[i - 1][j] + delete_cost, // 삭제
dp[i - 1][j - 1] + replace_cost // 교체
});
}
}
}
return dp[m][n]; // 최종 정렬 비용 반환
}
int main() {
string s1 = "INTENTION";
string s2 = "EXECUTION";
int insert_cost = 1;
int delete_cost = 1;
int replace_cost = 2;
int cost = sequenceAlignment(s1, s2, insert_cost, delete_cost, replace_cost);
cout << "최소 정렬 비용: " << cost << endl;
return 0;
}출력:
최소 정렬 비용: 8설명:
• s1과 s2는 정렬할 두 시퀀스입니다.
• insert_cost, delete_cost, replace_cost는 삽입, 삭제, 교체 연산의 비용을 나타냅니다.
• dp[i][j]는 s1의 첫 i글자와 s2의 첫 j글자를 정렬하는 데 필요한 최소 비용을 저장합니다.
• 각 위치에서 문자가 같으면 비용이 증가하지 않으며, 다르면 삽입, 삭제, 교체 중 최소 비용을 선택하여 dp[i][j]를 업데이트합니다.
• 최종적으로 dp[m][n]에는 전체 시퀀스를 정렬하는 데 필요한 최소 비용이 저장됩니다.
공간 복잡도 최적화
시퀀스 정렬도 공간 최적화를 통해 메모리 사용량을 줄일 수 있습니다. 현재는 2D DP 테이블을 사용하지만, 필요한 부분만 저장하여 1D DP 테이블로 줄일 수 있습니다.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 시퀀스 정렬을 다이나믹 프로그래밍으로 해결 (공간 최적화)
int sequenceAlignment_space_optimized(const string &s1, const string &s2, int insert_cost, int delete_cost, int replace_cost) {
int m = s1.length();
int n = s2.length();
// 현재 행과 이전 행을 저장할 2개의 1D 벡터
vector<int> prev(n + 1, 0);
vector<int> curr(n + 1, 0);
// 초기 조건: 한 시퀀스를 빈 시퀀스로 만드는 비용
for (int j = 0; j <= n; j++)
prev[j] = j * insert_cost;
// DP 테이블 채우기
for (int i = 1; i <= m; i++) {
curr[0] = i * delete_cost;
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
// 문자가 같으면 비용이 추가되지 않음
curr[j] = prev[j - 1];
}
else {
// 삽입, 삭제, 교체 중 최소 비용 선택
curr[j] = min({
curr[j - 1] + insert_cost, // 삽입
prev[j] + delete_cost, // 삭제
prev[j - 1] + replace_cost // 교체
});
}
}
// 현재 행을 이전 행으로 업데이트
prev = curr;
}
return prev[n]; // 최종 정렬 비용 반환
}
int main() {
string s1 = "INTENTION";
string s2 = "EXECUTION";
int insert_cost = 1;
int delete_cost = 1;
int replace_cost = 2;
int cost = sequenceAlignment_space_optimized(s1, s2, insert_cost, delete_cost, replace_cost);
cout << "최소 정렬 비용 (공간 최적화): " << cost << endl;
return 0;
}출력:
최소 정렬 비용 (공간 최적화): 8설명:
• 2D DP 테이블 대신 현재 행과 이전 행만 저장하는 1D DP 테이블을 사용하여 공간을 절약합니다.
• 이는 두 개의 1D 배열을 사용하여 이전 상태와 현재 상태만을 유지합니다.
'DataStructure > Algorithm' 카테고리의 다른 글
| Dynamic programming 연습문제 (0) | 2024.10.17 |
|---|---|
| Bucket Sort (버킷 정렬) (0) | 2024.09.23 |
| 3-way QuickSort (3분할 퀵정렬) (0) | 2024.09.16 |
| QuickSort (퀵정렬) (0) | 2024.09.16 |
| MergeSort (병합 정렬) (2) | 2024.09.15 |