Dijkstra1 [알고리즘] 다익스트라 알고리즘 Goal - 다익스트라 알고리즘을 이해하고 활용할 수 있다. ✔ - 다익스트라 알고리즘을 구현할 수 있다. ✔ 다익스트라 알고리즘 그래프 탐색 문제와 유사하나 정점 간의 간선에 가중치가 있어 경로 상의 가중치를 모두 더했을 때 가장 최소가 되는 경로를 구하는 문제이다. 그냥 그래프 탐색으로 모든 경로를 탐색하여 최솟값을 구할 수 있으나, 보통 시간 초과 오류가 난다. 다이나믹 프로그래밍을 사용해 그래프 탐색을 최대한 최소화 하는 것이 이 알고리즘의 기본 아이디어이다. 간단하게는 그래프 탐색과 다이나믹 프로그래밍을 함께 활용하는 것이라고 이해하면 좋다. 다익스트라 알고리즘의 원리 탐색을 시작할 점을 잡는다. (거리의 합이 중요하므로 시작점은 하나만 잡을 수 있다.) 해당 그래프 주위의 간선들을 탐색하여 그.. 2022. 8. 2. 이전 1 다음
