ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • LCA(Lowest Common Ancestor)
    알고리즘/자료구조 2016. 7. 30. 13:24

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


    가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 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뿐만 아니라 다른 형태의 문제를 풀 때도 유용하게 사용 할 수 있을 것 같다.

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

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

    댓글

Designed by Tistory.