최소 공통 조상
최소 공통 조상은 루트가 있는 트리에서 두 정점의 조상 중 깊이가 가장 큰 공통 정점을 구하는 문제다 트리 질의·그래프 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용...
| 분류 | 알고리즘 · 트리 질의·그래프 알고리즘 |
|---|---|
| 목적 | 루트가 있는 트리에서 두 정점의 조상 중 깊이가 가장 큰 공통 정점을 구하는 문제다 |
| 처리 방식 | 이진 리프팅은 각 정점의 2^k번째 조상을 전처리하고 두 정점의 깊이를 맞춘 뒤 높은 비트부터 조상을 비교한다 |
| 복잡도·성능 | 이진 리프팅 전처리 O(n log n), 질의 O(log n), 공간 O(n log n) |
| 필수 조건 | 트리의 루트·부모 관계와 깊이 정보가 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
최소 공통 조상은 루트가 있는 트리에서 두 정점의 조상 중 깊이가 가장 큰 공통 정점을 구하는 문제다 트리 질의·그래프 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 이진 리프팅은 각 정점의 2^k번째 조상을 전처리하고 두 정점의 깊이를 맞춘 뒤 높은 비트부터 조상을 비교한다. Euler tour와 RMQ로 환원하는 방법도 있다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 이진 리프팅 전처리 O(n log n), 질의 O(log n), 공간 O(n log n) 올바르게 적용하려면 트리의 루트·부모 관계와 깊이 정보가 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 트리 거리·경로 통계·계층적 종속 관계에 사용한다. 다양한 LCA 해법은 정적 트리인지 동적 트리인지에 따라 달라진다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]