동적계획법과 플로이드 알고리즘

알고리즘 ) 동적 계획법과 플로이드 알고리즘

 

동적 계획법, Dynamic Programming

동적 계획법의 원리는 매우 간단합니다.

일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여

최종적인 문제를 푸는 것입니다.

 

Step 1 : 문제의 답을 구하기 위한 recursive property를 세운다.

 

Step 2 : bottom-up 방식으로 작은 문제들을 먼저 풀면서 최종 문제를 풀겠다.

 

동적 계획 알고리즘은 최단경로 문제, 행렬의 제곱 문제 등의 최적화에 사용됩니다.

동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그중에 최적의 풀이법을 찾아내기 때문이죠.

 

 

플로이드의 최단 경로 알고리즘

플로이드 알고리즘은 각각의 정점(vertex)부터 모든 다른 정점으로 가는 최단경로를 찾는 알고리즘입니다.

 

만약 최단경로가 여러 개라면 그중 아무 최단경로를 하나 찾습니다.

 

 

각각의 정점으로부터 다른 정점으로 가는 비용을 2차원 배열에 담아 나타낸 사진 입니다.

∞표시는 하나의 정점에서 다른 정점으로 바로 가는 비용이 없을 때 표시합니다.

(V1에서 V3로 바로 가는 비용이 존재하지 않기 때문에 배열상에서 ∞로 표현합니다.

또한 자기 자신에게로 오는 비용이 존재하지 않기 때문에 0으로 표현합니다)

 

플로이드 알고리즘은 모든 정점에서 모든 정점으로 가는 최단경로를 다 구하기 때문에 2차원 배열을 사용하고

다익스트라 알고리즘은 특정한 노드 한 개에서 다른 노드로 가는 최단경로를 구하기 때문에 1차원 배열을

사용한다는 점이 플로이드 최단경로 알고리즘과 다익스트라 최단 경로 알고리즘의 차이점입니다.

 

 

 

최단경로로 갱신하기 위해 각각의 노드가 다른 노드로 갈 때 

첫 번째 노드를 거쳐 가는 경우

두 번째 노드를 거쳐 가는 경우

....

다섯 번째 노드를 거쳐가는 경우를 계산해서 최단 경로를 갱신해 주게 됩니다.

 

예를 들면 현재 2차원 배열에서 첫 번째 노드에서 3번째 노드로 가는 비용이 무한인데,

첫 번째 노드에서 두 번째 노드를 거쳐 세 번째 노드로 가는 비용은 4가 됩니다.

이경우 4는 무한 보다 비용이 작기 때문에 이차원 배열에서 값을 경신해 주게 됩니다.

 

즉 2차원 배열의 첫 번째 행은 0 1 4 1 5 가 되겠죠.

 

이런 식으로 2차원 배열의 비용이 모두 최단 경로로 갱신될 때까지 이 과정을 반복하게 된다면

2차원 배열에는 모든 경로로 가는 최단경로의 비용이 남게 될 것입니다.

 

플로이드 알고리즘의 시간 복잡도는 n^3입니다.