김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 11437 LCA 파이썬(Python)

문제 링크

최소 공통 조상(LCA)을 찾는 문제.
엄청 효율적으로 구현할 필요는 없고 나이브하게 구현해도 된다.
처음엔 별 생각 없이 \(log50000\)이면 약 \(15\) 쯤이니까 Straightforward하게 구현해도 되겠지라고 생각했는데, 해당 트리가 이진 트리라는 조건은 없기 때문에, 극단적인 Skewed Tree처럼 트리의 이점을 살리기 어려운 케이스가 있을 수 있다.
방법은 두 노드의 깊이를 같게 맞춰준 다음, 한 단계씩 올라가면서 공통 부모를 찾을 때까지 반복하면 된다.
이걸 위해서는 각 노드의 깊이와 부모를 알 필요가 있는데, 이건 트리를 순회하면서 업데이트해놓으면 된다.
최악의 경우는 루트 노드의 차수가 2고 나머지는 Skewed된 경우인데, 이 경우 약 25000번을 올라가야 한다.
따라서 시간을 좀 줄이기 위해 메모이제이션을 해주면 좋은데, 직접 리스트나 딕셔너리를 만드는 대신 간편하게 functools.cache를 사용했다.
생각보다 오랜 시간이 걸렸는데, Python의 재귀는 무겁고 꼬리 재귀 최적화(Tail Recursion Optimization)도 없다 보니 그런 것 같다.
또, LCA 알고리즘을 최적화하기 위해서는 부모를 한 단계씩 올라가는 게 아니라, 2의 제곱수만큼 올라갈 수도 있다.
그렇지만 전술한 것처럼 거기까지 효율적으로 구현하지 않아도 되기 때문에 쉽게 풀 수 있다.

#!python

from sys import stdin, setrecursionlimit
from collections import deque
from functools import cache
input = stdin.readline
# get_common_ancestor()가 최대 25000번 호출될 것이므로 넉넉하게 30000으로 설정
setrecursionlimit(30000)

# 메모이제이션을 위한 @cache 데코레이터
# a와 b가 같으면 그대로 반환하고 아니면 트리를 한 단계 위로 올라간다
# get_common_ancestor(1, 2)는 get_common_ancestor(2, 1)과 다르게 처리되어 메모이제이션의 이점을 살릴 수 없다
# 따라서 a가 b보다 작다는 것을 보장해야 한다
@cache
def get_common_ancestor(a, b):
    if a == b:
        return a
    return get_common_ancestor(min(parent[a], parent[b]), max(parent[a], parent[b]))

# 입력 처리 후 인접 리스트에 트리 담기
n = int(input())
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    v, w = map(int, input().split())
    tree[v].append(w)
    tree[w].append(v)

# parent[i]는 i번 노드의 부모 노드
# level[i]는 i번 노드의 깊이(1부터 시작)
parent = [0 for _ in range(n + 1)]
parent[1] = 1
level = [0 for _ in range(n + 1)]
# 트리를 순회하며 parent, level 리스트를 채움
q = deque([(1, 1)])
while q:
    node, lvl = q.popleft()
    for succ in tree[node]:
        if parent[succ]:
            continue
        parent[succ] = node
        level[succ] = lvl + 1
        q.append((succ, lvl + 1))

m = int(input())
for _ in range(m):
    a, b = map(int, input().split())
    # a와 b의 깊이를 같게 맞춰주고
    # 한 레벨씩 위로 올라가면서 공통 조상이 나오면 출력한다
    while level[a] > level[b]:
        a = parent[a]
    while level[b] > level[a]:
        b = parent[b]
    print(get_common_ancestor(min(a, b), max(a, b)))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑