Coding Interview Prep · 강의

우선순위 큐를 사용하는 다익스트라 알고리즘

Q: “우선순위 큐를 사용하는 다익스트라 알고리즘” 강의는 무료인가요?

네 — “우선순위 큐를 사용하는 다익스트라 알고리즘” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

Q: “우선순위 큐를 사용하는 다익스트라 알고리즘” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

heapq를 사용해 다익스트라 알고리즘을 구현하고, 가중치 그래프에서 완화 단계를 추적하며, k번 이하의 정류장을 거치는 최소 비용 항공편 문제를 해결합니다.

우선순위 큐를 사용하는 다익스트라 알고리즘은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

가중치 그래프의 최단 경로

다익스트라 알고리즘은 간선 가중치가 음수가 아닌 가중치 그래프에서 하나의 시작 노드부터 다른 모든 노드까지의 최단 경로를 찾습니다. 현재까지 알려진 최단 거리 순서대로 노드를 탐욕적으로 처리하며, 방문하지 않은 노드 중 현재 가장 가까운 노드를 항상 확장합니다. 핵심 자료 구조는 거리가 가장 작은 노드를 효율적으로 가져오는 최소 힙(우선순위 큐)입니다.

알고리즘 단계 개요

다익스트라 알고리즘은 다음과 같이 진행됩니다. (1) dist[source] = 0으로 초기화하고 dist[all others] = inf로 설정합니다. (2) (0, source)를 최소 힙에 삽입합니다. (3) 거리가 가장 작은 노드 u를 꺼냅니다. 더 작은 거리로 이미 방문한 노드라면 건너뜁니다. (4) u의 각 인접 노드 v에 대해 dist[u] + weight(u,v) < dist[v]이면 dist[v]를 갱신하고 (dist[v], v)를 힙에 삽입합니다. (5) 힙이 빌 때까지 반복합니다.

heapq를 사용한 파이썬 구현

파이썬의 heapq는 최소 힙을 구현합니다. 그래프는 인접 리스트로 표현합니다: graph[u] = [(v, weight), ...]. 힙에는 (distance, node) 튜플을 저장합니다. 더 나은 경로가 발견되기 전에 삽입된 항목인 오래된 힙 항목을 건너뛰기 위해 visited 집합을 사용합니다.

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

예제로 살펴보기

노드 5개와 다음 간선을 가진 그래프를 생각해 봅시다: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). 노드 0에서 출발하는 최단 경로는 다음과 같습니다. 1까지는 0→2→1을 거쳐 비용 3, 2까지는 비용 1, 3까지는 0→2→1→3을 거쳐 비용 4, 4까지는 0→2→1→3→4를 거쳐 비용 7입니다. 다익스트라 알고리즘은 특정 하나의 목표까지의 경로만이 아니라 이 모든 경로를 한 번의 순회로 찾습니다.

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

음수 가중치에서 다익스트라가 실패하는 이유

다익스트라의 정확성은 노드가 최소 힙에서 꺼내진 순간 해당 노드의 거리가 확정된다는 사실에 근거합니다. 이는 간선 가중치가 음수가 아닐 때만 성립합니다. 가중치가 -5인 음수 간선 u→v가 있으면, v를 방문한 뒤 u를 거치는 더 짧은 경로를 찾을 수 있습니다. 하지만 v는 이미 방문한 것으로 표시되어 있습니다. 음수 간선 하나만으로도 이후의 모든 거리 계산이 무효화될 수 있습니다.

K개 이하의 경유지를 거치는 최저가 항공편 (LeetCode 787)

이 문제에는 경유지가 최대 k개라는 제약이 추가됩니다. 기본 다익스트라는 단계 수를 기본적으로 처리하지 못합니다. 해결 방법은 상태를 (cost, node, stops_remaining)로 확장하는 것입니다. 이 3-튜플을 사용해 다익스트라를 수행하거나, k+1회 완화를 수행하는 벨만-포드를 사용합니다. 변형한 다익스트라는 남은 경유지가 0에 도달하면 중지하여 더 이상 이동하지 못하게 합니다.

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

시간 복잡도 분석

이진 힙을 사용하면 다익스트라는 O((V + E) log V) 시간에 실행됩니다. 각 정점은 한 번씩 꺼내지고(V번 꺼냄), 각 간선은 힙에 항목을 추가하게 될 수 있으며(E번 추가), 각 힙 연산의 비용은 O(log V)입니다. 피보나치 힙을 사용하면 시간 복잡도가 O(E + V log V)로 개선되지만, 파이썬의 heapq는 이진 힙입니다. 희소 그래프(E ≈ V)에서는 이진 힙 버전이 O(V log V)이고, 밀집 그래프(E ≈ V²)에서는 O(V² log V)입니다.

최단 경로 복원하기

거리뿐 아니라 실제 경로도 복원하려면 prev 배열을 유지합니다. dist[v]를 갱신할 때 prev[v] = u로 설정합니다. 알고리즘이 끝나면 역추적하여 시작점에서 목적지까지의 경로를 복원합니다. dst에서 시작해 source에 도달할 때까지 prev 포인터를 따라간 다음 결과를 뒤집습니다.

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    # Reconstruct
    path, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

희소 그래프에서 딕셔너리 사용하기

노드가 문자열이거나 연속되지 않은 정수일 때는 인접 리스트에 defaultdict(list)를 사용하고 거리에 일반 dict를 사용합니다. 이는 노드에 1부터 n까지 번호가 매겨지는 네트워크 지연 시간 같은 LeetCode 문제에서 흔히 사용됩니다. dist = {node: inf for node in all_nodes}를 사용하고 알고리즘이 끝난 뒤 도달할 수 없는 노드가 있는지 확인해야 합니다.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

가중치가 없는 그래프에서 BFS와 비교하기

가중치가 없는 그래프에서는 BFS가 O(V + E)에 최단 경로를 찾으므로 다익스트라의 O((V+E) log V)보다 빠릅니다. 다익스트라는 일반 FIFO 큐 대신 우선순위 큐를 using하여 가중치가 있는 그래프에 BFS를 확장 적용한 것입니다. 모든 간선의 가중치가 같으면 다익스트라는 BFS로 퇴화합니다. 가중치가 없는 그래프에는 BFS를, 음수가 아닌 가중치에는 다익스트라를, 음수 가중치에는 벨만-포드를 선택하십시오.

감소 키 최적화를 적용한 다익스트라

교과서적인 다익스트라는 키 감소 연산을 지원하는 우선순위 큐를 사용합니다. 노드의 거리가 개선되면 우선순위를 제자리에서 갱신하는 방식입니다. 이를 위해 O(E + V log V)를 달성하는 피보나치 힙이 필요하지만 구현하기는 어렵습니다. 면접에서 사용하는 지연 삭제 방식은 새 항목을 추가한 뒤 오래된 항목이 꺼지면 건너뛰므로, 상수 배수의 오버헤드만으로 더 간단하게 구현할 수 있습니다. 파이썬에서는 힙큐를 이용한 지연 삭제가 면접에서 표준적으로 사용되는 구현입니다.

빠른 확인

이 단원에서 다룬 자료 구조 & 알고리즘 — 코딩 면접 대비 개념에 대한 이해도를 확인해 보십시오.

단원 요약

이 단원에서는 다음을 배웠습니다. 다익스트라는 현재 최선의 거리 순서대로 노드를 탐욕적으로 처리하기 위해 최소 힙을 사용합니다. 다익스트라는 O((V+E) log V) 시간에 실행되지만 음수 가중치 간선에서는 실패합니다. 또한 노드를 꺼낼 때 방문 집합을 확인하여 오래된 힙 항목을 처리합니다. 다음으로는 n-1회의 완화를 통해 음수 가중치를 처리하는 벨만-포드를 살펴봅니다.

자주 묻는 질문