개발일지

개념 Lowest Common Ancestor의 약자로써 트리에서 가장 가까운 공통 조상을 찾는 알고리즘이다. 쉬운 방법으로 두 노드의 높이를 맞추고 하나씩 올라가면서 검사하는 방법이 있다. -> O(n) 시간 복잡도를 줄이는 방법 ancestor라는 2차원 배열을 만들고, ancestor[index][i] = index의 2^i 위에 부모노드를 저장하고 높이를 올릴 때 2^n단위로 올린다. -> O(logn) ancestor[index][i] = ancestor[ancestor[index][i - 1][i - 1] 작동원리 1. DFS를 사용하여 각 노드의 Level과 ancestor배열을 초기화한다. 2. 높이가 깊은 노드의 높이를 2^n 단위로 올리면서 맞춘다. 3. 두 노드가 같은 뿌리에 있으면 ..