0. 목차 1. 다익스트라 알고리즘 2. 최소비용 구하기(#1916) 1. 다익스트라 알고리즘 다익스트라 알고리즘은 DP를 이용한 대표적인 최단경로 알고리즘이다. 특정한 하나의 노드(출발점을 고정)에서 다른 모든 노드로 가는 최단 경로를 알려주는 알고리즘이다. 다익스트라 알고리즘의 핵심 개념만 요약정리하면 우선순위 큐(Heap)을 사용한다는 점 (최소 비용을 뽑아내기 위해) 이차원 배열에 값을 미리 저장(DP)해둔다는 점(그때그때 최단 경로/최소 비용 등 최솟값을 배열에 저장해두고 갱신하는 식으로) 다익스트라에서 음의 간선은 포함할 수 없다는 점 (음의 간선까지 고려 가능한 알고리즘은 벨만포드가 있다는데 이번에는 쓸일이 없어서 패스) 다익스트라와 DP 다익스트라 알고리즘은 하나의 최단거리를 구할 때 그 ..