LCA 썸네일형 리스트형 18. 최소 공통 조상 (LCA: Lowest Common Ancestor) 2 앞에서 최소 공통 조상(이하 LCA) 알고리즘을 통해 트리 내 두 노드의 공통 조상을 찾는 방법을 설명드린 적이 있었습니다. 트리 내 두 노드의 가장 가까운 조상을 찾는 LCA 알고리즘을 통하여 노드가 공유하는 조상 노드 중 가장 깊은 노드를 찾는 방법을 알게 되었습니다. 가장 원초적 형태의 LCA 알고리즘도 물론 강력한 기능을 갖고 있는 알고리즘이지만 이를 강화시킨 버전의 LCA 알고리즘을 이번 챕터에서 말씀드리려고 합니다. 크기가 그렇게 크지 않은 트리에서는 특정 노드에서 조상을 찾기 위해 올라가는 과정이 그렇게 멀지 않습니다. 두 노드를 비교하여 깊이가 더 깊은 노드의 깊이를 상대적으로 깊이가 얕은 노드에 맞춰주고, 부모로 올라가는 과정을 몇 번 거치면 쉽게 LCA를 구할 수 있었습니다. 문제가 되.. 12. 최소 공통 조상 (LCA: Lowest Common Ancestor) 최소 공통 조상은 트리구조에서 특정 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 트리구조라는 용어 자체가 생소하신 분들은 나무위키의 트리(그래프) 항목을 참고하시기 바랍니다. 트리(그래프) - 나무위키https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84) LCA(Lowest Common Ancestor) 알고리즘은 일반적으로 앞에서 이야기한 정의에 따라 가장 가까운 위치의 공통 조상을 찾는데 쓰이지만 이는 또한 두 노드의 가장 가까운 거리를 찾는다는 의미도 있기 때문에 노드간 거리를 구할 때도 사용됩니다. LCA 알고리즘은 단순하게 loop를 이용하여 공통조상을 찾는 방식과 DP나 세그먼트 트리를 이용하여 찾는 방식이 있습니다.. 이전 1 다음
