힙을 이용한 다익스트라
음이 아닌 간선에서 탐욕적으로 최단 경로를 찾습니다
힙을 이용한 다익스트라은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
최단 경로 문제
한 노드에서 다른 모든 노드까지 가는 가장 비용이 적은 경로를 구하려고 합니다. 모든 간선의 가중치가 0 이상이면 다익스트라 알고리즘으로 해결할 수 있습니다.
그리디 아이디어
다익스트라는 그리디 알고리즘입니다. 항상 방문하지 않은 노드 중 현재 알려진 거리가 가장 짧은 노드를 확장하고, 그 거리가 최종값이라고 판단합니다.
최소 힙을 사용하는 이유
가장 가까운 노드를 빠르게 꺼내려면 최소 힙이 필요합니다. 최소 힙은 느린 선형 탐색 대신 로그 n 시간에 가장 작은 거리를 반환합니다.
import heapq거리 초기화하기
모든 거리를 무한대로 설정한 다음 시작점의 거리를 0으로 바꿉니다. 도달하지 못한 노드는 계속 무한대로 남습니다.
dist = [float('inf')] * n
dist[src] = 0힙에 시작점 넣기
시작점을 (거리, 노드)의 튜플로 넣습니다. 거리를 앞에 두면 힙이 자동으로 비용을 기준으로 항목을 정렬합니다.
pq = [(0, src)]가장 가까운 노드 꺼내기
각 반복에서 가장 작은 (d, u)를 꺼냅니다. d는 u까지의 최단 거리이므로, 꺼낸 뒤에는 u에 대한 처리가 끝납니다.
d, u = heapq.heappop(pq)오래된 항목 건너뛰기
노드가 더 크고 오래된 거리와 함께 힙에 남아 있을 수 있습니다. d가 저장된 거리보다 크다면 해당 항목을 건너뜁니다.
if d > dist[u]:
continue이웃 노드 완화하기
완화란 이웃 노드의 거리를 더 작게 만들 수 있는지 확인하는 것입니다. u를 거쳐 가는 편이 더 저렴하면 거리를 갱신하고 해당 노드를 힙에 넣습니다.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))지연 삭제 기법
파이썬의 힙은 키를 갱신할 수 없으므로 같은 항목을 여러 번 넣고 오래된 항목은 무시합니다. 이 지연 방식은 코드를 짧고 빠르게 유지해 줍니다.
실행 시간
이진 힙을 사용하면 다익스트라 알고리즘은 O((V + E) log V) 시간에 실행됩니다. 간선이 수십만 개 있는 그래프도 쉽게 처리할 수 있습니다.
간선 가중치 확인하기
다익스트라는 음수 간선이 있으면 제대로 작동하지 않습니다. 꺼낸 거리도 최종값이 아닐 수 있기 때문입니다. 이런 경우에는 벨만-포드 알고리즘을 사용해야 합니다.
빠른 확인
(d, u)를 꺼냈는데 d가 dist[u]보다 큽니다. 어떻게 해야 하나요?
복습: 힙을 사용하는 다익스트라
거리를 초기화하고, (dist, node)를 넣고, 가장 가까운 항목을 꺼내고, 오래된 항목은 건너뛰고, 이웃을 완화합니다. 이것이 다익스트라 알고리즘이며 시간 복잡도는 O((V+E) log V)입니다. 🚀
자주 묻는 질문
“힙을 이용한 다익스트라” 강의는 무료인가요?
네 — “힙을 이용한 다익스트라” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“힙을 이용한 다익스트라”에서 뭘 배우나요?
음이 아닌 간선에서 탐욕적으로 최단 경로를 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“힙을 이용한 다익스트라” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 힙을 이용한 다익스트라
- 덱을 이용한 0-1 BFS
- 벨만-포드와 음의 간선
- 플로이드-워셜 모든 쌍 최단 경로