LCA(Lowest Common Ancestor)

알고리즘/자료구조 2016. 7. 30. 13:24 Posted by 아는 개발자

트리 내부에 있는 두개의 노드 사이의 최저 공통 조상을 효율적으로 찾아주는 자료구조이다.


가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 O(N)의 시간이 걸리지만


최적화된 LCA 알고리즘으로는 O(logN)시간만에 구할 수 있다.


LCA 알고리즘에서 트리의 노드들은 자신의 부모노드에 대한 정보외에 현재 높이에서 2^i 위에 위치한 조상노드에 대한 정보도 가지고 있다.

그림으로 표현하면 다음과 같다.


(자신의 부모노드 뿐만 아니라 2^i위치에 해당하는 조상노드의 정보를 가지는 것은 빠른 탐색을 할 때 유용하게 쓰인다.)


알고리즘의 절차는 다음과 같다.


1. 두 노드의 depth가 다르다면 depth를 맞춰준다.

* 이때 일일히 모든 부모노드를 방문하는 것이 아니라, 2^i에 대한 높이의 정보를 이용하면 신속하게 동일한 depth를 가지는 곳으로 이동 할 수 있다.

코드는 다음과 같다.



2. 가장 높은 조상부터 찾도록 하고 두 노드간의 공통조상이 다른 경우에는 그 위치부터 다시 조상을 찾도록 한다.



두 노드가 동일하거나, 두 노드의 공통조상이 모두 동일하다면 가장 낮은 조상을 return한다.


여기서 왜 공통조상이 아닐 때 재귀함수를 부르는지 이해가 가지 않았었다. 그래서 아예 가장 낮은 높이부터 조상들을 비교해 동일한 조상이 나오면 return하도록 했는데 이런경우 문제점은 공통 조상은 찾아주는데 최저 공통조상은 찾아줄 수 없다(높이 자체가 2의 지수 형태로 되어 있기 때문). 이때 찾는 공통 조상은 현재 위치에서 2의 지수 높이에 있는 공통 조상중 가장 낮은 위치에 있는 공통조상을 찾아주게된다.


동일한 level을 맞춰주기 위해 2^i의 형태로 이동했던 것 처럼 위 경우에도 가장 낮은 부분 부터 하나씩 올라가야 한다.


LCA 알고리즘의 가장 키 포인트는


2의 지수승에 해당하는 자료구조를 만들 때 최적화 효과를 볼 수 있다는것.


이런 아이디어는 LCA뿐만 아니라 다른 형태의 문제를 풀 때도 유용하게 사용 할 수 있을 것 같다.

728x90

'알고리즘 > 자료구조' 카테고리의 다른 글

모듈러 나눗셈 연산 처리하기  (2) 2016.12.10
완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05