Ⅰ. 최소 공통 조상 : 기초
https://www.acmicpc.net/problem/11437
N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M( 1 ≤ M ≤ 10,000 )개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
이 문제는 어떻게 해결할 수 있을까?
O ( NM )로 풀 수 있는 문제이기도 하다.
1. 최소 공통 조상( Lowest Common Ancestor) 알고리즘
두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘
예1) LCA(8번 노드, 15번 노드) → 2번 노드
예2) LCA(3번 노드, 15번 노드) → 1번 노드
2. 최소 공통 조상 알고리즘 동작 순서
LCA(8번 노드, 15번 노드)를 구해보자
1. 모든 노드에 대한 깊이(depth)를 계산 - DFS 이용
2. 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다.
3. 이후 부모가 같아질 때까지 한 칸씩 두 노드의 부모 방향으로 거슬러 올라간다.
4. 모든 LCA( a, b ) 연산에 대하여 3번의 과정을 반복
공통 조상은 2번 노드라는 것을 알 수 있다.
3. 파이썬으로 구현
import sys
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정
n = int(input())
parent = [0] * (n + 1) # 부모 노드 정보
d = [0] * (n + 1) # 각 노드까지의 깊이
c = [0] * (n + 1) # 각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)] # 그래프(graph) 정보
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):
# 먼저 깊이(depth)가 동일하도록
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))
4. 시간 복잡도 분석 - 한계
매 커리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도가 요구된다.
따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(NM) 이 된다.
Ⅱ. 최소 공통 조상 : 심화
https://www.acmicpc.net/problem/11438
N(2 ≤ N ≤ 100,000) 개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000) 개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
이 문제를 어떻게 해결할 수 있을까?
N, M의 크기가 커지면 위의 기초 알고리즘으로는 시간 초과 판정을 받는다.
기존 코드를 개선해보자.
1. 개선된 최소 공통 조상 알고리즘
1. 각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법에 대해 고민해보자
만약 총 15칸을 거슬러 올라가야 한다면,
8 → 4칸 → 2칸 → 1칸
2의 제곱 형태로 거슬러 올라가도록 하면 O(logN) 의 시간 복잡도를 보장할 수 있다.
메모리를 조금 더 사용하지만 각 노드에 대해 2^i 번째 부모에 대한 정보를 기록한다.
2. 모든 노드에 대하여 깊이(depth)와 2^i 번째 부모에 대한 정보를 계산한다.
예) 노드 15에 대한 2^i 번째 부모에 대한 정보를 계산
2. 개선된 최소 공통 조상 알고리즘의 연산 과정
LCA(13번 노드, 15번 노드) 를 구해보자
1. 모든 노드에 대한 깊이(depth)를 계산 - DFS 이용
2. 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다.
3. 이후 부모가 같아질 때까지 2의 제곱승 만큼씩 두 노드의 부모 방향으로 거슬러 올라간다.
4. 모든 LCA( a, b ) 연산에 대하여 3번의 과정을 반복
개선된 방식을 쓰면
노드의 개수가 많아질수록 만큼
많은 간격 만큼 점프할 수 있기 때문에 시간 복잡도가 많이 줄어든다.
3. 시간 복잡도 분석
- 다이나믹 프로그래밍을 이용하여 시간 복잡도를 개선할 수 있다.
- 참고로 세그먼트 트리를 이용하는 방법도 존재
- 매 쿼리마다 부모를 거슬러 올라가기 위해 O(logN)의 복잡도가 필요
- 따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(MlogN) 이다.
4. 파이썬 구현
(데이터가 1,000,000 개)
import sys
input = sys.stdin.readline # 시간 초과를 피하기 위한 빠른 입력 함수
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정
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)] # 그래프(graph) 정보
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][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
# 먼저 깊이(depth)가 동일하도록
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))
요약 최소 공동 조상 찾기 알고리즘의 동작 순서는 다음과 같다. 두 노드의 깊이가 동일할 때까지 올라간다. 부모가 같아질 때까지 거슬러 올라간다. 단, 데이터가 많을 때는 부모가 같아질 때까지 2의 제곱승 만큼 거슬러 올라간다. 시간 복잡도 : O(MN) → O(MlogN) |
출처
https://www.youtube.com/watch?v=O895NbxirM8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=15
'Computer Science > Algorithm' 카테고리의 다른 글
[백준] 선수과목 14567번 풀이 - 아직 못 품;; (0) | 2022.06.02 |
---|---|
[백준] 홀짝 칵테일 21312번 풀이 (0) | 2022.06.02 |
[이코테] 14강. 자료구조: 바이너리 인덱스 트리 (0) | 2022.06.01 |
[이코테 7강] 최단 경로 알고리즘 (0) | 2022.05.26 |
[이코테 3강] BFS & DFS (0) | 2022.05.19 |