0. 목차 1. 플로이드 와샬 개념 정리 2. 구슬 찾기 문제 풀이 3. 동전 2 풀이 (with DP) 1. 플로이드 와샬 개념 정리 개념 정리 출처: 나동빈 유튜브 플로이드 와샬 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. 다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 다익스트라가 출발점을 고정했을 때의 최단 경로만을 계산한다면 플로이드 와샬은 전체 통으로 스캔하는 개념이라고 생각하면 될듯. 하지만 여기서 무식하게 싹다 스캔하는 게 아니라 일종의 DP를 이용해 최단거리 노드를 기록한다. 시간복잡도 플로이드 와샬의 시간 복잡도는 O(n**3)이다. 점화식 Dab = min(Dab, Dak + Dkb)이며, 각 단계마다 ..
