[알고리즘] 6. Dynamic Programming

1. Brute force

2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound

여기서는 Dynamic Programming 에 대해 다룬다.

---

Dynamic Programming이란

• DP는 반복되는 계산을 공간메모리에 할당하여 공간복잡도로 시간복잡도를 줄이는 방식이다. 
• 주로 bruteForce, greedy나 재귀함수의 계산을 줄이며, 최적해를 보장한다.
• 중복되는 호출을 줄여 비효율을 줄이고, 큰 문제의 닮은 꼴의 작은 문제가 담길때(최적 부분구조) 쓸 수 있다.
• 가령 피보나치 수열의 경우 재귀적으로 구할 수 있지만 중복호출이 많고 시간이 오래 걸린다. 이때 DP로 해결할 수 있다.
• 분할정복 처럼 문제를 더 작은 문제로 나눈다는 점은 같지만, 각 문제가 독립적이진 않다. 
• 따라서 어떻게 더 작은 문제로 나눌 수 있을지 최적화된 구조를 생각하고, 최적의 규칙을 찾아야 한다. 그래서 Bottom-up 방식으로 구한다.

 

 

---

Dynamic Programming 예시

1. Longest common Subsequence
2. Warshall's Algorithm
3. Floyd's Algorithm
4. 0/1 Knapsack Problem
5. Bellman-Ford's Problem

---

Longest common Subsequence

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;


string findBestMatch(const string& baseWord, const vector<string>& candidates) {
    string bestMatch;      // 최적 단어
    int maxLCSLength = 0;  // 최대 LCS 길이
    // 각 후보 단어와 LCS 비교
    for (const string& candidate : candidates) {
        int n = baseWord.size();
        int m = candidate.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        // LCS DP 테이블 작성
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (baseWord[i - 1] == candidate[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        // 결과 출력 (비교 과정)
        cout << "Candidate: \"" << candidate << "\", LCS Length: " << dp[n][m] << endl;
        // 최적 단어 갱신
        if (dp[n][m] > maxLCSLength) {
            maxLCSLength = dp[n][m];
            bestMatch = candidate;
        }
    }
    return bestMatch;
}

int main() {
    vector<pair<string, vector<string>>> testCases = {
        {"intellagence", {"intelligence", "intelligentsia"}},
        {"accomodation", {"accommodation", "accommodative"}},
        {"enviroment", {"environment", "environ"}},
        {"managament", {"management", "managing"}},
        {"proffessor", {"professor", "profession"}}
    };

    // 각 테스트 케이스 실행
    for (const auto& [baseWord, candidates] : testCases) {
        cout << "\nBase Word: " << baseWord << endl;
        string bestMatch = findBestMatch(baseWord, candidates);
        cout << "Best Match: " << bestMatch << "\n";
    }

    return 0;
}

• 소위 LCS 라고 불리는 문제로 두 문자열에 들어있는 공통 부분 순서 중 가장 긴것을 찾는 문제다.
• 두 문자열 문자별로 가로와 세로에 두고, 2차원 표를 구성함으로써 해결할 수 있다.
• 표의 각 칸들은 앞에서부터 지금의 글자까지 비교했을때 나온 LCS의 값이다. 이처럼 부분문제로 나눌 수 있으니 DP를 적용할 수 있다.
• 글자가 다르면 왼쪽이나 위에서 큰 값을 내려받고, 글자가 같다면 좌상단 칸의 값에서 1을 더한다. 

---

Warshall's Algorithm

def warshall_algorithm(matrix):
    n = len(matrix) 
    closure = [row[:] for row in matrix] 
    for k in range(n):  # 중간 노드
        for i in range(n):  # 시작 노드
            for j in range(n):  # 도착 노드
                closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])

    return closure

# 주어진 인접 행렬
adjacency_matrix = [
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]


# Transitive Closure 계산
transitive_closure = warshall_algorithm(adjacency_matrix)

# 결과 출력
print("Transitive Closure:")
for row in transitive_closure:
    print(row)

• 방향성이 있는 그래프에서 각 정점을 이차원 배열로 나타낸다. 그래서 갈수 있다면 1,갈수 없다면 0이다.
• 한번에 직접 갈수 있는 상황인 초기 그래프만 주어질때, 여러번 거쳐서 갈 수 있는 곳도 가능하다면 1로 표시해야한다.
• i->j로 바로 갈수 없는 상황이라도, i->k 로 갈 수 있고, k->j로 갈 수 있다면, i->j로 갈 수 있다는 것을 뜻한다. 
• 즉 arr[i][k]와 arr[k][j] 가 1이라면 arr[i][j]도 1로 바꾸면 된다.
• 그래서 경유지 k와 시작지 i,도착지 j가 3중으로 for문이 돌게 된다. 이때 경유지 K가 가장 중요하다. K가 for문의 가장 위에 와야 하는것이 핵심이다. 우선 경유해서 갈 수 있는 모든 경우를 확인해야 한다. A에서 C까지 갈수 있는지 없는지를 확인하기 위해서는 그전에 A->B와 B->C가 가능한지, A->D와 D->C가 가능한지...경유지를 먼저 따져야 하기 때문이다.

---

Floyd's Algorithm

def warshall_algorithm(matrix):
    n = len(matrix) 
    for i in range(n):  # 시작 노드
        for j in range(n):  # 도착 노드
            if matrix[i][j] == "∞":  
                matrix[i][j] = float('inf')  
    
    # closure 복사 (초기화)
    closure = [row[:] for row in matrix] 

    for k in range(n):  # 중간 노드
        for i in range(n):  # 시작 노드
            for j in range(n):  # 도착 노드
                # 중간 노드를 경유하는 것이 더 짧다면 갱신
                if closure[i][j] > closure[i][k] + closure[k][j]:
                    closure[i][j] = closure[i][k] + closure[k][j]

    return closure

# 주어진 인접 행렬
adjacency_matrix = [
    [0, 3, "∞", 1, "∞", 7, "∞", 15, 3, 9],
    ["∞", 0, 8, "∞", 3, "∞", 4, 55, "∞", "∞"],
    [3, "∞", 0, 2, "∞", 11, "∞", 19, 8, "∞"],
    ["∞", 2, "∞", 0, 6, "∞", 4, "∞", 1, "∞"],
    [1, 1, 3, "∞", 0, 1, 10, 3, "∞", 1],
    ["∞", "∞", 3, "∞", 6, 0, 4, "∞", 3, "∞"],
    [3, 1, "∞", 9, "∞", 5, 0, 10, 2, "∞"],
    ["∞", 2, 7, 12, 3, 7, "∞", 0, "∞", 5],
    [4, 14, "∞", 5, "∞", 3, "∞", 5, 0, 3],
    ["∞", 12, 1, "∞", 7, "∞", 3, "∞", 5, 0]
]


transitive_closure = warshall_algorithm(adjacency_matrix)

# 결과 출력
for row in transitive_closure:
    print(row)

 

• 워셜 알고리즘과 같은 원리를 사용하되 거리가 1과 0으로 표시되지 않고 숫자가중치로 있는 경우이다.
• 가는 길이 없는경우에는 무한으로 표시되며, 가장 짧은 최단 경로를 저장하면 된다.
• 워셜 알고리즘과 같은 원리로 경유지를 중심으로 현재 적혀있는 최단 경로와 경유해서 가는 것 중 더 적은 값을 선택하게 하면 된다. 

---

0/1 Knapsack Problem

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    fastio;
    long long n=8,limit=50;
    long long arr[n][limit+1]={0};
    int weights[8] = {5, 10, 8, 7, 4, 6, 3, 9};
    int values[8] = {20, 40, 35, 25, 15, 30, 10, 50};
    int weight=weights[0];
    int value = values[0];
    for(int i=0; i<weight; i++){
        arr[0][i]=0;
    }
    for(int i=weight; i<limit+1; i++){
        arr[0][i]=value;
    }
    //첫 행의 물건 무게보다 작은 열에는 0, 물건 무게보다 큰열에는 가치를 넣는다.
    //첫 행에는 점화식을 사용할 수 없으므로 다음과 같이 할당한다.     
    for(int j=1; j<n; j++){
        weight=weights[j];
        value = values[j];
        for(int i=0; i<limit+1; i++){
            arr[j][i]=arr[j-1][i];
            //일단 모든 행의 값을 이전 행에서 할당받는다.
        }
        for(int i=0; i+weight<limit+1; i++){
            if(arr[j-1][i+weight]<arr[j-1][i]+value){
                arr[j][i+weight]=arr[j-1][i]+value;
                //이번에 넣을지 말지 정할 물건의 넣었을때 가치와(arr[j-1][i]+value)
                //넣지 않았을때의 가치 (arr[j-1][i+weight])를 비교해 큰 값을 할당한다.
            }
        }
        
    }
    cout<<arr[n-1][limit];
    
    return 0;
}

• 냅색문제로, 왼쪽 행은 각 물건들 위쪽의 열은 넣을 수 있는 배낭 용량이다. 그래서 최대의 가치를 기록한다.
• 모든 행의 값을 이전 행에서 할당받는데 점화식을 사용할 수 없으므로 첫행과 첫열은 초기화가 필요하다. 
• 점화식의 핵심은 이번에 넣을지 말지 정할 물건의 넣었을때 가치(arr[j-1][i]+value), 넣지 않았을때의 가치 (arr[j-1][i+weight])를 비교해 큰 값을 할당한다.
• dp[i][w]는 "i번째 물건까지 고려하고, 배낭 용량이 w일 때 얻을 수 있는 최대 가치"를 저장하는 테이블이다. dp[i][w]의 값을 계산하는 과정에서, i번째 물건을 넣을지 또는 넣지 않을지를 결정합니다.
• 넣을 수 없다면(넣지 않는다면)  dp[i][w] = dp[i-1][w] 가 된다.
• 물건을 넣는다면  dp[i][w] = dp[i-1][w - wi] + vi 

	용량
물건 index	가치합

---

Bellman-Ford's Problem

def bellman_ford(graph, start):
    # 그래프에서 각 노드의 최단 거리를 무한대로 초기화
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    
    # 부모 노드를 추적할 딕셔너리 초기화
    parent = {node: None for node in graph}
    
    # 그래프에서 최대 (노드 수 - 1)번 만큼 반복하여 최단 거리 계산
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u]:
                if distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight
                    parent[v] = u  # 부모 노드를 기록
    
    # 음수 사이클 탐지: 마지막에 한번 더 반복해서 갱신되는 노드 찾기
    negative_cycle_node = None
    for u in graph:
        for v, weight in graph[u]:
            if distance[u] + weight < distance[v]:
                negative_cycle_node = v  # 음수 사이클이 존재하는 노드
                break
        if negative_cycle_node:
            break

    if negative_cycle_node is None:
        # 음수 사이클이 없다면 최단 경로와 경로를 출력
        print("음수 사이클 없음")
        for node in graph:
            print(f"최단 경로 ({start} -> {node}): {distance[node]}")
            path = []
            current = node
            while current is not None:
                path.append(current)
                current = parent[current]
            path.reverse()
            print(f"경로: {' -> '.join(path)}")
        return distance
    else:
        print("음수 사이클 존재")
        return None

# 그래프 정의 (간선 정보)
graph = {
    's': [('t', 6),('y',7)],
    't': [('x', 5),('y',8),('z',-4)],
    'x': [('t', -2)],
    'y': [('x', -3),('z',9)],
    'z': [('s', 2),('x',7)]
}

# Bellman-Ford 알고리즘 실행
start_node = 's'
bellman_ford(graph, start_node)

• 또 주어진 경로에 대해 다른 것들을 거쳐서 갈 수 있는 최단 거리를 구하는 문제다.
• 워셜, 플로이드 알고리즘과 유사하나 이 알고리즘은 음수 가중치 까지 처리한다. 
• 이때 음수로 된 싸이클이 생기면 그냥 그 안에서 뺑뺑돌며 수치를 음의 무한으로 만들 수 있으니 있어서는 안된다.
• 음수 가중치로 경로를 거칠때 오히려 값이 낮아질 수 있으므로 모든 간선을 전부 확인하며 최단거리를 찾는다. 
• 만약 마지막 까지 다 확인했는데도 갱신이 된다면 그것은 음의 무한루프에 빠진것으로 간주한다.

---

결론

Dynamic Programming에 관한 내용이었다.