이전 포스팅 digraph에서 이행적 폐쇄를 설명하면서 dp를 잠깐 언급했다.
동적계획볍(Dynamic Programming, DP)은 divide-conquer와 같이 알고리즘 설계 기법 중 하나다. digraph의 이행적 폐쇄를 모두 구하기 위해 모든 정점에 대한 dfs를 하면 O(n+m)을 n번 수행한다. dp는 이렇게 지수 시간이 걸리는 문제 해결에 주로 사용한다.
DP
dp는 하나의 큰 문제를 여러 개의 작은 문제로 나누어 작은 문제 해결 결과를 기억하고 큰 문제를 해결하는 방법이다.
DP 특성
dp 적용을 위해서는 다음과 같은 문제 특성이 있어야 한다.
- Overlapping
- 부문제(subproblems)들이 각 독립적이지 않은 상호 겹쳐짐이 있어야 한다. 따라서 해결을 상향식으로 구축할 수 있도록 한다.
- Optimal Substructure
- 부문제의 결과값을 통해 전체 문제의 최적치를 낼 수 있어야 한다.
피보나치 수열 예시
DP의 대표적 예시로 피보나치 수열 문제가 있다. 피보나치 수열은 f(0) = f(1) = 1, f(n) = f(n-1) + f(n-2) 로 정의된다.
작은 문제에서 해결을 시작해 큰 문제를 해결하는데 분할정복과 dp 방법으로 비교해보자.
분할정복
그림의 예시로 f(6)이 원문제가 된다. 원문제 해결을 위해 f(5), f(4)를 구하는 문제로 쪼개진다. 계속해서 부문제들이 밑으로 쌓이게 되는데 예를 들어 f(5) 호출로 인해 f(3) 호출을 f(4)에서도 똑같이 호출하게 되는 중복이 발생한다. 따라서 f(6)이 아닌 f(100)같은 원문제를 분할정복으로 풀게 되면 수많은 중복으로 호출이 기하급수적으로 늘어난다.
dp는 분할정복 방법의 중복 문제를 해결한다.
dp
dp는 f(0)과 f(1)을 기억하고 시작한다. 기억을 바탕으로 f(2)를, f(3)를 구하고 점차 원문제 f(6)을 해결한다. 분할정복과 달리 dp는 초기 부문제에서 출발해 원문제에 접근한다.
📌 Floyd-Warshall 알고리즘
digraph에서 이행적 폐쇄를 구하기 위한 Floyd-Warshall 알고리즘 역시 초기 그래프 G를 G[0]에 복사하는, 초기 부문제에서 시작한다.
Floyd-Warshall 알고리즘은 모든 정점에 번호를 매기고, 임의 정점 i부터 k를 경유해 또 다른 임의 정점 j에 도달하는 경로가 있는지를 확인한다. k는 1부터 시작해 마지막 정점 n까지 늘려가며 k 경유 경로를 확인할 때는 k의 이전까지의 정점들을 사용한다.
Floyd-Warshall 의사코드
Alg Floyd-Warshall()
input Graph G
output transitive closure G[n]
Numbering of the vertices of G //정점 번호 매김
G[0] <- G //그래프 복사
for k <- 1 to n {
G[k] <- G[k-1] //이전 그래프 복사
for i <- to n (except i = k) {
for j <- 1 to n (except j = i, k) {
if(G[k-1].areAdjacent(v[i], v[k]) && G[k-1].areAdjacent(v[k], v[j])){
if(!G[k].areAdjacent(v[i], v[j]){
G[k].insertDirectedEdge(v[i], v[j], k)
}
}
}
}
}
return G[n]G[k]는 1 ~ k-1 정점을 경유 정점으로 사용하는 그래프다.
k단계에서 G[k-1]로 부터 G[k]를 계산한다. G[k]에서 k를 거쳐가는 i->j를 찾아야 하므로, 모든 정점쌍 (i, j)에 대해서 (i,k), (k, j)가 존재하고 (i, j)가 G[k]에 없는 상황이면 i->j 방향 간선을 추가한다.
Floyd-Warshall 알고리즘 시간복잡도는 O(n^3)이다.
모든 정점에 dfs를 하는 것보다 시간복잡도는 dp 방식이 더 크게 나온다. 하지만, dp는 이미 계산된 부문제의 해결을 기억해 재사용하기 때문에 연산의 중복을 피할 수 있어 그래프 밀집도가 크거나 반복적인 이행적 폐쇄를 구하는 문제 해결에서 dp 방식의 채택이 더 좋다.
참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.
