본글에서는 ‘최소 공통 조상(LCA; Lowest Common Ancestor)’ 구하기 문제 중 하나인 ‘최소 공통 조상 구하기 2’에 대해
탐구해보겠습니다. 이 문제는 특정 트리 구조에서 두 노드의 최소 공통 조상을 찾는 문제로,
특히 이진 트리에서 이루어집니다. LCA 문제는 트리 탐색 및 조작과 관련된 기본적인 문제로,
코딩 인터뷰 및 알고리즘 경시대회에서도 자주 등장합니다.
문제 설명
주어진 이진 트리가 있을 때, 두 노드 u와 v의 최소 공통 조상을 찾아야 합니다.
이진 트리는 각 노드가 최대 2개의 자식을 가질 수 있으며, 루트 노드부터 시작하여
각각의 노드는 고유한 값을 가집니다.
입력 형식
- 첫 번째 줄: 노드의 수
n(1 ≤ n ≤ 100,000) - 두 번째 줄: 트리의 구성 (부모 노드와 자식 노드가 주어짐)
- 세 번째 줄: 두 개의 노드
u,v
출력 형식
노드 u와 v의 최소 공통 조상을 출력합니다.
예제
입력: 7 1 2 1 3 2 4 2 5 3 6 3 7 4 5 출력: 2
문제 접근 방법
이 문제를 해결하기 위해, 먼저 트리를 구성해야 합니다. 트리를 배열로 표현하거나 연결 리스트로 표현할 수 있지만,
연결 리스트를 사용하는 것이 더 효율적입니다. 이후 DFS(Depth First Search)를 통해 각 노드의 깊이를 기록하고,
부모 노드를 저장하여 이후 LCA를 쉽게 찾을 수 있습니다.
트리 구성
주어진 간선 정보를 바탕으로 노드와 자식 관계를 설정합니다.
파이썬의 딕셔너리를 사용하여 부모-자식 관계를 저장합니다.
from collections import defaultdict
def build_tree(edges):
tree = defaultdict(list)
for parent, child in edges:
tree[parent].append(child)
return tree
DFS를 통한 깊이 및 부모 노드 정보 저장
def dfs(tree, node, parent, depth, depths, parents):
depths[node] = depth
parents[node] = parent
for child in tree[node]:
if child != parent:
dfs(tree, child, node, depth + 1, depths, parents)
LCA 함수 구현
깊이를 기준으로 두 노드의 위치를 맞춘 후, 그들의 부모를 따라 올라가면서
두 노드가 같은 노드에 도달할 때까지 진행합니다.
def lca(u, v, depths, parents):
# Depth 맞추기
if depths[u] < depths[v]:
u, v = v, u
while depths[u] > depths[v]:
u = parents[u]
while u != v:
u = parents[u]
v = parents[v]
return u
전체 코드
def main():
n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
u, v = map(int, input().split())
tree = build_tree(edges)
depths = {}
parents = {}
# DFS를 통해 깊이와 부모 정보 수집
dfs(tree, 1, -1, 0, depths, parents)
# 최소 공통 조상 찾기
ancestor = lca(u, v, depths, parents)
print(ancestor)
if __name__ == "__main__":
main()
시간 복잡도
위의 알고리즘의 시간 복잡도는 O(n)입니다. 트리를 구성하고 탐색하는 과정에서
각 노드를 한 번씩 방문하기 때문입니다.
결론
‘최소 공통 조상 구하기 2’ 문제는 이진 트리의 탐색 및 조작의 기초를 이해하는 데 도움이 되며,
실제로 유용한 알고리즘입니다. 이 문제를 해결하는 과정에서 트리의 구조와 DFS의 개념을 깊이 있게 이해할 수 있게 됩니다.
이 알고리즘은 이후 다양한 문제들로 확장 가능하며, 다른 자료구조와의 응용에도 큰 도움이 됩니다.