제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.
목차 :
- 다익스트라 알고리즘_개념
- 리스트를 사용한 다익스트라
- 최소 힙을 사용한 다익스트라
- 시간복잡도 분석
- 그리디한 선택이 최적해를 보장함 야매 증명
다익스트라 알고리즘_개념
얘는
- 그리디임. 가장 작은 것부터 선택해나감.
- 음수 간선을 허용하지 않음. (음수간선을 허용하면 그리디하게 할 수 없기 때문, 벨만 포드 알고리즘은 코테 거의 x)
출발 정점은 문제에서 보통 주어지는데, 우린 0번 정점에서 출발한다고 가정하자.
5번 정점까지 가는 최단거리를 구하라 했다고 생각해보자.
- 해당 정점까지의 현재까지의 최단 거리를 저장한 distance 리스트 정의
- 해당 정점까지의 최단 거리가 확정되었는지 여부를 저장이한 T F visited 리스트
- distance[start] = 0 : 시작 정점에서 시작 정점까지는 거리가 0이라 생각
- 방문하지 않은 정점 중 distance[x]가 최소인 정점을 관찰
- 그 정점에 대한 최단 거리를 확정함. (즉, visited[x] = True로 함.)
- 인접 정점(= 새로 최단거리 확정한 정점에 인접해 있는 정점)에 대한 거리갱신 (distance[x]와 최단거리 타고 간 거리 비교)
- n번만큼 4 ~ 6 반복
이 때, 5번에서 그냥 최단거리라는 걸 어떻게 확정지을 수 있냐? 하는데, 여기선 음의 간선을 허용하지 않으므로, 그냥 그리디하게 당장 최소인 놈을 최단 거리 확정해버려도, 최종적인 최단 거리를 보장함.
n번 반복하는 이유는, 그리디하게 매 반복마다 visited를 하나씩 True로 만들어주기 때문.
리스트를 사용한 다익스트라
https://dailyalgo.kr/ko/problems/29
위 문제에 대한 풀이로 설명.
리스트를 사용할 경우, 시간복잡도는 `O(V^2 + E) = O(V^2)` (단, V는 정점 개수, 여기선 n)
여기서 중요한 건, distance가 가장 작은 놈을 뽑고 그걸 방문처리할 수 있는 이유는,
만약 그게 최단 거리가 아니고 다른 경로를 타고타고 가서 그 경로가 더 최소가 될 수 있었다면(ex. 4 대신 1 1 1로 3으로), 그쪽 경로(1 걸리는 경로)가 애초에 먼저 선택되었을 것이기 때문에,
그냥 그리디하게 distance가 가장 작은 놈 뽑으면 그게 전체 solution에 포함되는 최단 거리이기 때문!! 그래서 내가 그리디 알고리즘에 따라 뽑은 놈은 무조건 거기까진 최단거리가 보장된거고, 확정된거고, True로 방문처리할 수 있는거임.
def solution(n, edges):
def dijkstra(node):
# 3. 시작 정점까지 가는 최단거리 0으로
distance[node] = 0
# 7. 4 ~ 6단계를 n번 반복 - O(V)
for _ in range(n):
# 1. distance에서 최단 거리의 정점을 뽑는다.
node, min_dist = -1, INF
for i in range(1, n + 1): # - O(V)
if not visited[i] and distance[i] < min_dist:
node = i
min_dist = distance[i]
# 2. 최단 거리를 확정
visited[node] = True
# 3. 해당 정점과 인접한 정점에 대해 최단 거리를 갱신
# 여기는 프로그램 내내 O(E * 상수배)정도 걸림.
# 같은 간선을 여러 번 조회할 수도 있기 때문.
for next_node, dist in graph[node]:
next_dist = min_dist + dist
if not visited[next_node] and next_dist < distance[next_node]:
distance[next_node] = next_dist
# 주어진 간선 정보 edges는 단방향 간선이라는 것에 유의.
graph = [[] for _ in range(n + 1)]
# 파이썬에서 대문자로 작성하면 보통 상수. infinity의 줄임말.
# 저렇게 하면 float타입 (부동 소수점 타임)의 양의 무한대 실수가 생성이 됨.
INF = float("inf")
# 1. distance 리스트 생성
distance = [INF] * (n + 1)
# 2. visited 리스트 생성
visited = [False] * (n + 1)
for x, y, w in edges:
graph[x].append((y, w))
# 단방향 간선이니, 반대는 하지 않음.
# 다익스트라 시작!!
dijkstra(1)
# 1번 정점부터 n번 정점까지 가는 최단 거리가 이제 저기 담김.
return distance[n]https://www.acmicpc.net/problem/1916
아래 코드는 위 문제에 대한 풀이로, 좀 더 자세히 주석처리한 버전
import sys
input = sys.stdin.readline
# 입력 : 정점 개수, 버스 개수, 간선 정보들, 출발 정점과 도착 정점
# 출력 : 출발 정점 -> 도착 정점 최소 비용
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
x, y, w = map(int, input().split())
graph[x].append((y, w))
s, t = map(int, input().split())
def dijkstra(node):
# 3. 시작 정점까지의 최단 거리는 0으로
distance[node] = 0
# 7. 4. ~ 6. 단계를 n번 반복
# for _ in range(n):
for _ in range(n - 1):
# 사실, 위처럼 n - 1까지 돌아도 됨!
# 왜냐면, n - 1번째에 이미 distance[t] 갱신하고 끝남.
# 4. 방문하지 않은 놈들 중에서, distance(최단 거리) 가장 작은 놈 찾기
# 5. 최단 거리를 확정
# 6. 걔랑 인접한 놈들 distance(최단 거리) 갱신
# 4. 아직 방문하지 않은 놈들 중에서, distance(최단 거리) 가장 작은 놈 찾기
node, min_dist = -1, INF
for i in range(1, n + 1):
# 아직 방문하지 않은 놈들중에 가장 최단 거리가 작은 놈이
# 최종적으로 node와 min_dist에 저장되도록 할 것임.
# 이 부분 로직 좀 헷갈릴수도 있는데... 잘 생각하자.
if not visited[i] and distance[i] < min_dist:
node = i
min_dist = distance[i]
# 이제, 여기까지 했으면
# node에는 현재 미방문 노드들 중 최단 거리가 최소인 노드가,
# min_dist에는 그 최소인 최단 거리가 저장됨.
# 5. 최단 거리를 확정
visited[node] = True
# 여기서, 이렇게 백트래킹할 수 있다!!
# t가 이미 적중하면 그냥 끝내면 됨.
if node == t:
return
# 6. 해당 정점과 인접한 정점에 대해 최단 거리를 갱신
# 이 "해당 정점과 인접한 정점" 정보는, 그래프(인접 리스트)에서 빼오면 됨.
for next_node, dist in graph[node]:
# 일단 선조치 후반영 마인드로 갈 거임.
# 일단 그 최소 최단 거리 정점에서 타고 간 최단 거리(임시) 정의
next_dist = min_dist + dist
# 그리고, 여기서 실제로 반영을 해줄지 말지 정함.
# 아직 거기 최단거리 확정 안 났으면서(방문 안 했으면서),
# 내가 타고타고 간 최단 거리가, 이미 들어가 있는 최단 거리보다 작으면:
# 그 때 비로소 반영을 한다.
# if not visited[next_node] and next_dist < distance[next_node]:
# 사실, 아래처럼만 짜도 됨!
# 왜냐하면, 이미 visited인 놈이면, 무조건적으로 next_dist가 더 큼!!
if next_dist < distance[next_node]:
distance[next_node] = next_dist
# next_dist는 그 인접한 정점까지 가는 한 칸 거리,
# next_node는 그 인접한 정점.
# next_node가 이미 최단거리 확정된 놈이면,
# 최단거리에서 다른 거 타고 간 놈은, 무조건적으로
# 이미 최단거리 확정난 거리보다 크다!!
INF = float('inf')
# 1. distance 리스트 정의
distance = [INF] * (n + 1)
# 2. visited 리스트 정의
visited = [False] * (n + 1)
dijkstra(s)
print(distance[t])최소 힙을 사용한 다익스트라
https://www.acmicpc.net/problem/1753
위 문제를 가지고 설명. 위 문제는 리스트를 사용해 풀었을 때 시간 초과가 나, 힙을 사용한 다익스트라로 풀어야 한다.
다익스트라의 6단계
- 시작 정점 초기화
- 힙이 빌 때까지
- 힙에서 하나 뽑아서
- 쓰레기 값이면 튕기기
- 그 정점에 인접한 정점들에 대해,
- 거기에서 가는 거리가 더 짧으면 distance 갱신
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
s = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
x, y, w = map(int, input().split())
graph[x].append((y, w))
INF = float('inf')
distance = [INF] * (n + 1)
def dijkstra(node):
# 1. 시작 노드 distance 초기화
distance[node] = 0
heap = [(0, node)]
# 2. 힙이 빌 때까지
while heap:
# 3. 힙에서 하나 뽑아서
min_dist, node = heappop(heap)
# 4. 쓰레기 값이면 튕기기
if min_dist > distance[node]:
continue
# 5. 그 노드 기준으로 인접한 노드들에 대해
for next_node, dist in graph[node]:
# 새롭게 갱신할 지 말지 관찰할 next_node의 거리는,
# 내가 보는 기준인 node까지의 최단 거리 + 거기서 next_node까지의 거리
next_dist = min_dist + dist
# 6. 새로 본 거리가 더 짧으면 distance 갱신
if next_dist < distance[next_node]:
distance[next_node] = next_dist
heappush(heap, (next_dist, next_node))
dijkstra(s)
for d in distance[1:]:
if d == INF:
print('INF')
else:
print(d)힘을 쓰면 레거시(쓰레기값)이 힙에 들어있다 하더라도, min_dist에는 더 짧은 애들이 먼저 빠져나오고, 그 담에 더 긴게 들어와도 continue로 튕겨나가기 때문에, visited는 필요 없음.
그래서, 사실은 visited는 필요가 없다!
시간복잡도 분석
시간복잡도는 일단 우리 구현에서는 최악의 경우 `O(ElogE)`. pop이 logE인데, 이걸 E번 반복하니까 ElogE.
왜 E번 반복하냐? 하면, 저 `while heap:` 부분이 `최악의 경우 O(E)로 반복된단` 건데, 그 이유는 각 정점의 관점에서 우리가 인접한 간선들을 통해 갱신되는 튜플을 힙에 넣을 지 말지 고민하는 거잖음? 여기서 그 튜플을 고민한다는 것 자체가 그 간선을 고민한다는 거고,
한 간선이 힙에 여러 번 들어갈 수도 있으며, 모든 간선이 한 번 이상 무조건 조회되기에 대략 `O(E * 상수배)`정도 걸린다고 볼 수 있는 거임.
근데 이게 `pop에 logE, push에 logE`니까 엄격히 따지면 대략 `O(2E상수배*logE)` 정도로 볼 수 있음. 빅 오 표기법에 따라 이는 `O(ElogE)`가 됨.
근데, 우리는 보통 힙을 이용한 다익스트라는, 일반적으로 O(ElogV라고 말함.
왜냐하면, 완전 그래프에선 E = V(V-1) 이니 E = V^2인데, (O는 생략)
정확히 말하면, E는 V^2보다는 살짝 작잖음. V(V-1)이기도 하고, 완전그래프가 잘 나오는 것도 아니니까.
그래서, 여기에 log를 씌우면, logE = O(log(V^2)) = O(2log(V)) = O(log(V))가 됨.
그래서, O(ElogE)는 일반적인 그래프 입력에서는 대충 보면 O(ElogV)가 되니까, 일반적으로 다익스트라의 시간복잡도를 O(ElogV)라고 부름.
근데, 이러한 설명은 ‘나동빈’님 그 알고리즘 책에서 그렇게 설명하는 것 같고, 사실 실제로는 위 나무위키의 3번 구현을 우리가 구현한 거고, 실제론 2번으로 구현하게 될 경우가 O(Elog(V))에 더 가깝게 시간복잡도가 나오는 것 같다.
하지만, 저 2번도 O(Elog(V))에 가까운거지 O(Elog(V))는 아니기에 어느정도 근사라든지 가정 같은 걸 써야하는데, 그럴거면 3번인 우리 구현도 위에 설명대로 가정을 해서 O(Elog(V))라고 충분히 설명할 수 있다. 아마 저 설명도 그래서 할 수 있는 공식적인 설명인듯.
결국, 힙을 사용한 다익스트라의 시간복잡도는 일반적으로 O(Elog(V))라고 한다고 생각하면 될 듯하다.
그리디한 선택이 최적해를 보장함 야매 증명
기본정리)
- 힙에서 어떤 튜플(가중치도 포함해 본 관점)을 빼냈다는 건, 그 노드의 주변 노드들을 그 튜플 관점에서 관찰하겠다는 거임. 이 과정에서 주변 노드들의 distance가 전부 next_dist보다 이미 작아서 아무 distance도 갱신되지 않을 수도 있음. 그럼에도 관찰할 필요성은 있다.
- 튜플에서 나와 실제로 첫 번째 if문을 통과해 인접 노드들을 평가하게 되는 건, 각 정점당 한 번씩만 일어남. 단, while heap: 부분은 최악의 경우 O(E)번 일어남.
- 힙에 들어가는 튜플들은 인접 노드들의 distance를 갱신할 가능성이 존재하는 놈들이다. 물론, 힙에 들어간 튜플들이 다 힙에서 안튕기고 나오지도 못하고, 안튕기고 나오더라도 인접 노드들의 distance를 갱신하지 못할 수도 있다. 가능성이 존재하는 것.
심화내용)
- 만약 (6, 4)가 힙에 없는 상태에서 (7, 4)가 힙에 들어가고 나왔다면, (6, 4)는 힙에 새로 들어갈 리가 없다!!! 왜냐하면, 알고리즘 원리상 (6, 4) 경로가 존재했다면, 힙에서 먼저 걔가 결국 나왔을 것이기 때문. 그게 되게 먼 경로라고 하더라도, 앞에 꺼보단 힙에서 결국 먼저 빠진다!!!
- 만약 (7, 4)가 들어가 있는 상태에서, (7, 4)가 힙에서 나오기 전에 (6, 4)이 힙에 들어갔다면, (더 작은 (5, 4)같은 놈이 존재하지 않다면) (6, 4)가 힙에서 먼저 나오고, 그 이후에 (7, 4)는 힙에서 나올 때 첫 번째 if문에서 튕겨버린다. 그래야 이미 힙에 있는 걸 튕길 수 있지. 여기서 튕기는 이유는, (6, 4)가 들어갈 때 distance가 갱신됐기 때문임.
- 만약 (6, 4)가 들어가 있는 상태라면, (7, 4)는 힙에 들어가지조차 못한다. distance값을 힙에 넣을 때 갱신해주기 때문에, (7, 4)가 들어가려고 할 때 두 번째 if문에서 튕기기 때문. 그래야 먼 경로에서 이걸 관측했을 때 튕길 수 있지.
정리 및 결론)
- ‘힙에 들어간다’고 최단 경로 확정인 건 아님. (10, 4)가 앞서 인접해서 먼저 힙에 들어갈 수 있지만, (7, 4)같은 게 있으면, (10, 4)가 나오기 전에 무조건 (7, 4)가 힙에 들어가고 (더 작은 게 없다면) 무조건 (7, 4)가 힙에서 먼저 나옴.
- 그러나, 힙에서 그 정점에 대한 튜플이 처음으로 나왔으면, 그 튜플은 최단 경로가 확정임. 즉, ‘힙에서 가장 처음으로 나오’면 최단 경로가 확정임.
위 그림 예시에서 2 → 3과 3 → 4 간선 가중치가 1이라고 생각하고 예시 들어보면 이해하기 편함.
결론은, 다익스트라 알고리즘에서는 그리디하게 힙에서 당장 최소 가중치인 튜플을 골라가기만 하면, 그게 전체의 최적해(최단 거리가 최소화되는 해)가 됨이 증명됨.
과제 및 풀이 정리
- 다익스트라 알고리즘
- 최소 비용 구하기
- 최단 경로
- 특정 거리의 도시 찾기
- 서강그라운드
- 녹색 옷 입은 애가 젤다지?
- 특정한 최단 경로
- 미확인 도착지
'Algorithms & Languages > 25-1 파이썬 알고리즘 코딩캠프' 카테고리의 다른 글
| [알고리즘 코딩캠프 후기] 2주간의 수업 수강을 마친 후기 및 성과 (0) | 2025.03.01 |
|---|---|
| [알고리즘 코딩캠프 10일차] 백준 4문제 모의고사 시행 (0) | 2025.03.01 |
| [알고리즘 코딩캠프 8일차] 유니온 파인드, 최소 신장 트리(MST), 크루스칼 알고리즘 (0) | 2025.02.27 |
| [알고리즘 코딩캠프 7일차] 트리, 이진 트리, 이진 트리의 순회, 힙, 우선순위 큐 (0) | 2025.02.24 |
| [알고리즘 코딩캠프 6일차] 순열, 조합, 중복순열, 중복조합, 백트래킹 (0) | 2025.02.23 |
