플로이드 워셜

플로이드-워셜(Floyd-Warshall) ?

• 각각의 모든 노드에 대하여 다른 모든 노드로의 최단 거리를 구할 수 있는 알고리즘 ! ↔ 특정 시작점에서 다른 모든 노드로의 최단 거리를 구하는 다익스트라, 벨만-포드 알고리즘

• 음수 가중치를 갖는 간선이 있어도 수행 가능하나, 음수 사이클이 있는 경우엔 사용할 수 없다.

💡 플로이드 워셜 핵심 개념 - 동적 계획법(DP)

• DP는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 후에, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하기 위한 알고리즘이다 ! → **기억하며 풀기**(Memoization)

  1. 메모이제이션 : 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고, 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결한다.

  2. 점화식 만들기 : 변수 간의 관계식을 만드는 것이라고 보면 된다. ( ex: 피보나치 수열 f(n) = f(n-1) + f(n-2) )

<aside> 💡

DP를 적용시킬 수 있는 조건 ?

1. 중복되는 부분 문제 (Overlapping Sub-problems)

• DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구하기 때문에, 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능한 것 !

1. 최적 부분 구조 (Optimal Substructure)

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다 ! </aside>

• DP 문제 해결 방식

  • Bottom-Up → 반복문 사용(최적 부분 구조 보장)
  • Top-Down → 재귀 사용(Memoization 활용)

💡 플로이드 와샬 - 구현

• 시간 복잡도: O(V^3) → 노드 수(V)가 작을 경우 효율적이다. ( 일반적으로 V ≤ 500 정도가 적합하다고 한다. )