반응형
최소공유조상
-
LCA(Lowest Common Ancestor) / 최소 공통 조상 알고리즘알고리즘/개념 정리 2020. 12. 27. 01:26
LCA(Lowest Common Ancestor) / 최소 공유 조상 목차 1. LCA란? 2. O(N) LCA 알고리즘 3. O(logN) LCA 알고리즘 LCA란? LCA란 말 그대로 최소 공유 조상이다. 그래프에서 두 노드 각각의 부모들을 쭉 타고 올라갔을 때 최초로 공유하는 부모를 말한다. 이 예시에서 노드 5와 노드 3의 최초 공유 조상은 1이 된다. 이 경우에 노드 12와 노드3의 최소 공유 조상은 1이 된다. O(N) LCA 알고리즘 자 그러면 이제 LCA 알고리즘을 구현해 봅시다. LCA 구현을 위해 3가지 단계가 필요합니다. 각 노드들의 depth를 구하여 가지고 있는다 ( depth : root 노드부터 자기 노드까지의 거리(깊이)) LCA를 구하려는 두 노드 중 더 깊은 노드의 dep..