이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
Dijkstra, Bellman-Ford, Floyd-Warshall shortest paths, Kruskal and Prim MST, topological sort.
음수 가중치 없음 → Dijkstra (가장 빠름)오늘은 그래프 심화 알고리즘을 배워보겠습니다.
지난 시간에 BFS로 최단 경로를 찾았는데요, 그건 간선 가중치가 모두 같을 때만 맞아요.
만약 도로마다 거리가 다르면 어떻게 해야 할까요?
그림 왼쪽의 결정 트리를 보세요.
먼저 "모든 쌍의 최단 거리가 필요한가"를 판단합니다.
네라면 Floyd-Warshall, 아니라면 다음 질문으로 넘어가요.
"음수 가중치가 있는가"를 확인하는 거죠.
음수가 있으면 Bellman-Ford를 선택해야 합니다.
음수가 없고 가중치가 있으면 Dijkstra가 가장 빠른 선택이에요.
비가중 그래프라면 그냥 BFS면 충분하고요.
오른쪽 비교표를 보시면 네 알고리즘의 시간 복잡도가 정리되어 있어요.
Dijkstra는 힙을 쓰면 O((V+E)logV)로 상당히 빠릅니다.
Bellman-Ford는 O(VE)로 좀 느리지만 음수를 처리할 수 있어요.
Floyd-Warshall은 O(V³)인데 모든 쌍을 한번에 구하니까 그만한 가치가 있죠.
여기서 중요한 건 "왜 Dijkstra는 음수에서 실패하는가"입니다.
Dijkstra는 한번 확정한 거리를 다시 바꾸지 않는 그리디 방식이에요.
음수 간선이 있으면 확정 후에 더 짧은 경로가 발견될 수 있거든요.
이게 바로 Bellman-Ford가 필요한 이유입니다.
Dense 그래프, 즉 간선이 많은 경우에는 Floyd가 유리하고요.
Sparse 그래프에서는 Dijkstra가 압도적으로 빠릅니다.
이 네 가지 알고리즘을 하나씩 자세히 살펴볼게요.
선생님: BFS로 구한 최단 경로가 항상 맞는 건 아니라고 했는데, 왜 그런 건가요?
학생: 음, BFS는 간선 수 기준으로 탐색하니까 가중치가 다르면 의미가 없어서요?
선생님: 맞아요. BFS는 "몇 칸" 떨어졌는지만 보지, "얼마나 비싼지"는 안 봐요.
학생: 그러면 간선이 2개인 경로가 1개인 것보다 더 짧을 수도 있는 거네요?
선생님: 정확해요. 가중치 1+1=2가 가중치 10 하나보다 짧죠. 그래서 Dijkstra가 필요한 거예요.
학생: 그런데 왜 Dijkstra는 음수에서 안 되는 거예요?
선생님: Dijkstra는 "지금 가장 짧은 거리의 정점은 더 줄어들 수 없다"고 가정해요.
선생님: 음수 간선이 있으면 이 가정이 깨져서 이미 확정한 거리가 틀릴 수 있답니다.