[알고리즘] 벨만 포드, 바이너리 인덱스 트리, 최소 공통 조상
* 음수 간선이 포함된 상황에서의 최단 거리 문제에서 사용
* 모든 간선의 비용이 양수일때는 다익스트라 최단 경로 알고리즘을 사용
벨만 포드 최단 경로 알고리즘
① 모든 간선이 양수인 경우
② 음수 간선이 있는 경우
ⓐ 음수 간선 순환은 없는 경우
ⓑ 음수 간선 순환이 있는 경우
* 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있음.
=> 음수간선의 순환을 감지할 수 있음
=> 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느림.
<동작순서>
① 출발 노드를 설정
② 최단 거리 테이블을 초기화
③ 다음 과정을 N-1번 반복
ⓐ 전체 간선 E개를 하나씩 확인.
ⓑ 각 간선을 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신
=> 만약 음수 간선 순환이 발생하는지 체크하고싶다면 3번의 과정을 한 번 더 수행(이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것.)
* 다익스트라 알고리즘
: 매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택.
: 음수 간선이 없다면 최적의 해를 찾을 수 있음.
*벨만 포드 알고리즘
: 매번 모든 간선을 전부 확인
: 다익스트라 알고리즘에서의 최적의 해를 항상 포함
: 다익스트라 알고리즘에 비해 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있음.
import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정
def bf(start):
#시작 노드에 대해서 초기화
dist[start] = 0
#전체 n번의 라운드를 반복
for i in range(n):
#매 반복마다 모든 간선을 확인
for j in range(m):
cur = edges[j][0]
next_node = edges[j][1]
cost = edges[j][2]
#현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 갱신
if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
dist[next_node] = dist[cur] + cost
#n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
if i == n - 1:
return True
return False
#노드, 간선의 개수 입력 받기
n,m = map(int, input().split())
#모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
#최단 거리 테이블을 모두 무한으로 초기화
dist = [INF] * (n+1)
#모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
#a번 노드에서 b번 노드로 가는 비용이 c라는 의미
edges.append(a,b,c)
#벨만 포드 알고리즘을 수행
negative_cycle = bf(1) #1번이 시작노드
if negative_cycle:
print("-1")
else:
#1번 노드를 제외한 다른 모든 노드로 가기 위한 최단거리 출력
for i in range(2, n+1):
#도달할 수 없는 경우, -1 출력
if dist[i] == INF:
print("-1")
#도달할 수 있는 경우 거리를 출력
else:
print(dist[i])
바이너리 인덱스 트리(BIT : Binary Indexed Tree)
* 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조.(=펜윅 트리 fenwick tree)
* K & -K 연산
* 바이너리 인덱스트리 업데이트 : 특정 값을 변경할 때는 0이 아닌 마지막 비트만큼 더하면서 구간들의 값을 변경
* 누적 합(Prefix Sum) : 1부터 N까지의 합 구하는 방법은 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합 계산
import sys
input = sys.stdin.readline
#데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k)
n, m, k = map(int, input().split())
#전체 데이터의 개수는 최대 1,000,000개
arr = [0] * (n + 1)
tree = [0] * (n + 1)
#i번째 수까지의 누적 합을 계산하는 함수
def prefix_sum(i):
result = 0
while i>0:
result += tree[i]
#0이 아닌 마지막 비트만큼 빼가면서 이동
i -= (i & -i)
# i번째 수를 dif 만큼 더하는 함수
def update(i, dif):
while i<=n:
tree[i] += dif
i += (i & -i)
# start부터 end까지의 구간 합을 계산하는 함수
def interval_sum(start, end):
return prefix_sum(end) - prefix_sum(start - 1)
for i in range(1, n+1) :
x = int(input())
arr[i] = x
update(i, x)
for i in range(m + k):
a, b, c = map(int, input().split())
#업데이트 연산
if a==1:
update(b, c - arr[b]) #바뀐 크기(dif)만큼 적용
arr[b] = c
#구간 합(interval sum) 연산
else :
print(interval_sum(b, c))
최소 공통 조상 (LCA:Lowest Common Ancestor)
* 최소 공통 조상 문제는 두 노드의 공통된 조상 중 가장 가까운 조상을 찾는 문제.
<동작 과정>
① 모든 노드에 대한 깊이를 계산 : DFS를 이용
② 최소 공통 조상을 찾아 두 노드를 확인
ⓐ 먼저 두 노드의 깊이가 동일하도록 거슬러 올라감
ⓑ 이후 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감
③ 모든 LCA(a,b) 연산에 대해 2번의 과정을 반복
import sys
sys.setrecursionlimit(int(le5)) #런타임 오류 피하기
n = int(input())
parent = [0] * (n+1) #부모 노드 정보
d = [0] * (n+1) #각 노드까지의 깊이
c = [0] * (n+1) #각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)] #그래프 정보
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
#루트 노드부터 시작해 깊이(depth)를 구하는 함수
def dfs(x, depth) :
c[x] = True
d[x] = depth
for y in graph[x] :
if c[y]: #이미 깊이를 구했다면 넘기기
continue
parent[y] = x
dfs(y, depth + 1)
#A와 B의 최소 공통 조상을 찾는 함수
def lca(a,b):
#먼저 깊이가 동일하도록
while d[a] != d[b]:
if d[a] > d[b]:
a = parent[a]
else:
b = parent[b]
#노드가 같아 지도록
while a != b:
a = parent[a]
b = parent[b]
return a
dfs(1, 0) #루트 노드는 1번 노드
m = int(input())
for i in range(m) :
a, b = map(int, input().split())
print(lca(a,b))=> 최악의 경우 모든 쿼리를 처리할 때 시간 복잡도는 O(NM)이다.
* 개선하기 : 메모리를 조금 더 사용해 각 노드에 대해 2^i 번째 부모에 대한 정보를 기록해둔다.
=> 다이나믹 프로그래밍을 이용해 시간 복잡도를 개선할 수 있음(세그먼트 트리를 이용하는 방법도 존재)
=> 모든 쿼리를 처리할 때 시간 복잡도는 O(MlogN)이다.
import sys
input = sys.stdin.readline #시간 초과를 피하기 위해 빠른 입력 함수
sys.setrecursionlimit(int(le5)) #런타임 오류를 피하기 위한 재귀 깊이 제한 설정
LOG = 21 #2^20 = 1,000,000
n = int(input())
parent = [[0] * LOG for _ in range(n + 1)] # 부모 노드 정보
d = [0] * (n + 1) #각 노드까지의 깊이
c = [0] * (n + 1) #각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)] #그래프 정보
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
#루트 노드부터 시작해 깊이를 구하는 함수
def dfs(x, depth):
c[x] = True
d[x] = depth
for y in graph[x]:
if c[y] : #이미 깊이를 구했다면 넘기기
continue
parentl[y][0] = x
dfs(y, depth + 1)
#전체 부모 관계를 설정하는 함수
def set_parent():
dfs(1,0) #루트 노드는 1번 노드
for i in range(1, LOG):
for j in range(1, n+1):
parent[j][i] = parent[parent[j][i - 1]][i - 1]
#A와 B의 최소 공통 조상을 찾는 함수
def lca(a,b):
#b가 더 깊도록 설정
if d[a] > d[b]:
a, b = b, a
#먼저 깊이가 동일하도록
for i in range(LOG, -1, -1, -1) :
if d[b] - d[a] >= (1 << i) :
b = parent[b][i]
#부모가 같아지도록
if a==b :
return a;
for i in range(LOG, -1, -1, -1) :
#조상을 향해 거슬러 올라가기
if parent[a][i] != parent[b][i]:
a = parent[a][i]
b = parent[b][i]
#이후 부모가 찾고자 하는 조상
return parent[a][0]
set_parent()
m = int(input())
for i in range(m)
a, b = map(int, input().split())
print(lca(a, b))
이코테 2021 강의를 듣고 정리한 글이다