다익스트라
import heapq
def dijkstra(n): # O(ElogV)
hq = [(0, n)]
dis[n] = 0
while hq:
cur_dis, cur_x = heapq.heappop(hq)
if cur_dis > dis[cur_x]:
continue
for i, w in graph[cur_x]:
new_dis = cur_dis + w
if dis[i] > new_dis:
dis[i] = new_dis
heapq.heappush(hq, (new_dis, i))
벨만 포드
def bellman_ford(n): # O(VE)
min_d = [float('inf')] * (v + 1)
min_d[n] = 0
for i in range(v):
for j in range(e):
a, b, w = graph[j]
d = min_d[a] + w
if min_d[a] != float('inf') and min_d[b] > d:
min_d[b] = d
if i == v - 1: # 무한 루프 체크
return [-1]
return min_d
플로이드 워셜 링크
def floyd(n): # O(n³)
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
pre[i][j] = pre[k][j]
유니온 파인드 링크
def find(x):
if parent[x] < 0:
return x
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return False
if parent[x] > parent[y]:
x, y = y, x
parent[x] += parent[y]
parent[y] = x
return True
최소 스패닝 트리 링크
- Kruskal 링크
O(ElogE)
- Prim 링크
O(VlogV + ElogV)
세그먼트 트리
tree = [0 for _ in range(size * 4)]
def update(node, start, end, idx, diff) :
if idx < start or idx > end :
return
tree[node] += diff
if start != end :
mid = (start + end) // 2
update(node * 2, start, mid, idx, diff)
update(node * 2 + 1, mid + 1, end, idx, diff)
def sum(node, start, end, left, right) :
if left > end or right < start :
return 0
if left <= start and end <= right :
return tree[node]
mid = (start + end) // 2
return sum(node * 2, start, mid, left, right) \
+ sum(node * 2 + 1, mid + 1, end, left, right)
KMP 링크
def getPi(str):
m = len(str)
j = 0
pi = [0] * (m)
for i in range(1, m):
while j > 0 and str[i] != str[j]:
j = pi[j - 1]
if str[i] == str[j]:
j += 1
pi[i] = j
return pi
def kmp(str1, str2):
n = len(str1)
m = len(str2)
pi = getPi(str2)
j = 0
ret = []
for i in range(n):
while j > 0 and str1[i] != str2[j]:
j = pi[j - 1]
if str1[i] == str2[j]:
if j == m - 1:
ret.append(i - m + 1)
j = pi[j]
else:
j += 1
return ret