Algorithms (9) 썸네일형 리스트형 LCA - 최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘이란?트리에서의 두 정점 u, v에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 즉, 가장 가까운 공통 조상은 두 정점 u, v를 자손으로 가지는 노드들 중 깊이가 가장 깊은 노드를 의미합니다. 이 글에서는 LCA를 2가지 방법으로 구해보겠습니다. 첫 번째는 O(N)만에 구할 수 있는 알고리즘이고 두 번째 방법은 O(logN)만에 구할 수 있는 알고리즘입니다. 1. O(N) 알고리즘지금 소개해 드릴 이 방법은 간단합니다. 먼저 알고리즘부터 살펴보겠습니다.[알고리즘] 1. 두 정점 u, v의 깊이가 같은지 확인합니다. 만약 두 정점의 깊이가 다르다면 두 정점의 깊이가 같아질 수 있도록 한 칸씩 트리를 타고 올라가면서 깊이를 맞춰줍니다. 2. 두 .. 이전 1 2 다음
