다익스트라&플로이드&동적계획법

다익스트라 알고리즘

 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

 

동작 단계

① 출발 노드와 도착 노드를 설정한다.
② '최단 거리 테이블'을 초기화한다.
③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
④ 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.
⑤ ③~④의 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

 

플로이드-워셜 알고리즘

• 플로이드-워셜
  • 다익스트라: 출발점을 정했을 때 다른 노드에 이르는 최단거리.
  • 플로이드-워셜: 모든 지점에서 다른 모든 지점까지 최단거리.자기자신으로 가는 비용은 0
  • 직접 연결되어있지 않은 경로는 무한대.
  • $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$
   

 

동적계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 

 

동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다.

즉, 우리가 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 된다. F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼, 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다.

이처럼 문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있다. 그러나 다른 점은, 그 결과를 기록하고 이용한다는 점이다.

 

결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고, 문제를 쪼갤 수 있는 구조를 **겹치는 부분 문제(Overlapping Subproblem)**라고 한다.

아까 예시에서 설명했던 부분에서 각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것을 겹치는 부분 문제, 이미 실험했던 내용은 기록해두고 쓰면 된다는 것을 메모이제이션 이라고 생각하시면 된다.

즉, 겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데, 이 때 사용하는 방법은 메모이제이션을 이용하는구나라고 생각하면 된다.