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개 중 2번째 강의입니다.

Q: “벨만-포드와 음수 사이클” 강의는 얼마나 걸리나요?

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

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

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

모든 간선에 대해 n-1번 완화 과정을 수행하고 마지막 과정으로 음수 사이클을 탐지하며, 음의 가중치 간선에서 다익스트라 알고리즘이 실패하는 이유를 설명합니다.

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

벨만-포드가 필요한 이유

벨만-포드는 다익스트라처럼 단일 시작점 최단 경로 문제를 해결하면서도 음수 간선 가중치를 처리합니다. 또한 음수 사이클도 감지합니다. 음수 사이클은 전체 가중치의 합이 음수인 사이클로, 이를 통과하는 유한한 최단 경로를 정의할 수 없게 만듭니다. 다익스트라보다 느리지만 그래프에 음수 가중치 간선이 포함될 수 있다면 벨만-포드가 올바른 선택입니다.

완화: 핵심 연산

벨만-포드는 하나의 연산인 완화를 기반으로 합니다. 간선 (u, v, w)를 완화한다는 것은 다음을 의미합니다. dist[u] + w < dist[v]이면 dist[v] = dist[u] + w로 갱신합니다. 모든 간선을 반복해서 완화합니다. 핵심은 다음과 같습니다. 음수 사이클이 없는 그래프에서 모든 최단 경로는 간선을 최대 V-1개 포함합니다. 따라서 모든 간선에 대해 V-1회 완화를 수행하면 모든 최단 경로를 찾을 수 있습니다.

벨만-포드 구현

그래프를 간선 목록 [(u, v, weight)]으로 표현합니다. dist[source] = 0으로 초기화하고 나머지는 모두 inf로 설정합니다. V-1회 반복하면서 매 회차 모든 간선을 완화합니다. V번째 회차에도 갱신이 발생한다면 음수 사이클이 있다는 뜻입니다.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

V-1회 반복으로 충분한 이유

음수 사이클이 없는 그래프에서 최단 경로는 각 노드를 최대 한 번씩 방문하므로 간선을 최대 V-1개 포함합니다. 1회차가 끝나면 간선 1개를 사용하는 최단 경로가 최적이 됩니다. 2회차가 끝나면 간선 2개를 사용하는 최단 경로가 최적이 됩니다. V-1회차가 끝나면 간선을 최대 V-1개 사용하는 모든 최단 경로를 찾게 됩니다. V회차에도 거리가 갱신된다면 시작점에서 도달할 수 있는 음수 사이클이 그래프에 포함되어 있다는 뜻입니다.

음수 사이클 감지

V-1회차를 수행한 뒤 모든 간선에 대해 한 번 더 반복합니다. 어떤 간선 (u, v, w)가 dist[u] + w < dist[v]를 만족하면 음수 사이클이 존재하며 일부 노드까지의 최단 경로는 -infinity가 됩니다. 실제 활용 사례로는 통화 환전에서 차익 거래 기회 감지(log 가중치 그래프의 음수 사이클)와 제약 조건 시스템의 불일치 감지가 있습니다.

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

다익스트라와 벨만-포드 비교

다익스트라: O((V+E) log V), 음수가 아닌 가중치가 필요하며 탐욕적인 방식입니다. 벨만-포드: O(V × E), 음수 가중치를 처리하고 음수 사이클을 감지합니다. 음수가 아닌 가중치를 사용하는 대부분의 면접 문제에서는 다익스트라를 선호합니다. 음수 가중치가 등장하는 경우(예: ‘음수 비용 간선이 있는 최단 경로 찾기’ 또는 ‘차익 거래 감지’)에는 벨만-포드가 정답입니다. 밀집 그래프에서는 벨만-포드의 최악 시간 복잡도 O(V³)이 플로이드-워셜과 비슷합니다.

활용: 벨만-포드를 이용한 최저가 항공편

K개 이하의 경유지를 거치는 최저가 항공편(LeetCode 787)은 변형한 벨만-포드로 해결할 수 있습니다. 정확히 k+1회의 완화를 수행합니다(k개의 경유지는 간선 k+1개를 의미합니다). 한 번의 반복에서 허용된 이동 횟수를 초과하지 않도록 이전 회차의 거리 복사본을 사용해야 합니다. 그렇지 않으면 한 번의 반복 안에서 여러 이동을 연쇄적으로 사용할 수 있습니다.

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

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

SPFA: 큐 기반 최적화

최단 경로 신속 알고리즘(SPFA)은 거리가 방금 갱신된 노드에서 출발하는 간선만 큐를 using하여 다시 완화하는 최적화된 벨만-포드입니다. 평균적인 경우의 시간 복잡도는 O(E)이지만 최악의 경우에는 여전히 O(V × E)입니다. SPFA는 면접에서 거의 필요하지 않지만, 벨만-포드가 희소 그래프에서 너무 느릴 때 최적화 방법으로 언급할 수 있습니다. 파이썬에는 기본 제공 SPFA가 없지만 collections.deque를 사용하면 쉽게 구현할 수 있습니다.

통화 차익 거래 감지

벨만-포드의 고전적인 활용 사례입니다. 통화 환율이 주어졌을 때 차익 거래가 가능한지, 즉 통화를 환전한 뒤 시작할 때보다 더 많은 금액이 돌아오는 사이클이 있는지 감지합니다. 환율에 음의 로그를 취해 변환합니다. 차익 거래 = 총 log 가중치가 음수인 사이클 = 벨만-포드로 감지할 수 있는 음수 사이클입니다. 이렇게 하면 실제 금융 문제를 표준 알고리즘에 대응시킬 수 있습니다.

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

조기 종료 최적화

모든 간선을 한 번 완화하는 동안 거리가 한 번도 갱신되지 않았다면 이후 회차에서도 아무것도 갱신되지 않으므로 일찍 종료합니다. 이 최적화를 적용하면 그래프가 몇 번의 회차만으로 이미 최적 상태가 되었을 때 최선의 경우 시간 복잡도를 O(E)로 줄일 수 있습니다. 각 회차를 시작할 때 updated = False 플래그를 추가하고, 회차가 끝난 뒤에도 False로 남아 있으면 즉시 종료합니다.

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

인접 리스트를 사용하는 그래프에서의 벨만-포드

그래프가 간선 목록이 아니라 인접 리스트로 주어졌다면 먼저 간선 목록으로 변환하거나, 모든 인접 리스트 항목을 간선으로 순회합니다. V=1000이고 E=5000이면 V-1=999회차에서 매번 5000개의 간선을 검사하므로 연산 횟수는 4,995,000번이며, 이는 시간 제한 안에서 충분히 처리할 수 있습니다. 매우 밀집한 그래프(E ≈ V²)에서는 최악의 경우 O(V³)이 플로이드-워셜과 같으므로 상황에 따라 선택해야 합니다.

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

빠른 확인

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

단원 요약

이 단원에서는 다음을 배웠습니다. 벨만-포드는 음수 가중치 간선을 처리하기 위해 모든 간선을 V-1회 완화합니다. V번째 완화 회차에도 개선 사항이 발견되면 음수 사이클을 의미합니다. 또한 알고리즘의 시간 복잡도는 O(V × E)로, 다익스트라의 O((V+E) log V)보다 큽니다. 다음으로는 한 번의 O(V³) 계산으로 모든 쌍의 최단 경로를 구하는 플로이드-워셜을 살펴봅니다.

자주 묻는 질문