최소 조상 알고리즘1 [알고리즘] 최소 공통 조상(LCA) 알고리즘 🧩 최소 공통 조상(LCA) 알고리즘 최소 공통 조상(LCA): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 여기서 3번 노드와 11번 노드의 공통 조상 노드는 1번이다. ✔️ 동작 과정 모든 노드에 대한 깊이(depth)를 계산 최소 공통 조상을 찾을 두 노드를 확인 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복한다. 1) 모든 노드 깊이 계산 우선 DFS를 이용해서 루트 노드에서부터의 깊이를 구한다. 2) 공통 조상을 구할 노드 선택 두 노드의 깊이를 맞춰주고, 거슬러 올라간다. 그렇게 2번 노드가 공통 조상임을 찾을 수 있다! .. 2023. 12. 10. 이전 1 다음 반응형
