알고리즘

# 최소 공통 조상 (LCA) 정점 A와 정점 B가 각각 자신을 포함하여 초상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 구하기 처음 아이디어 = 정점의 부모를 따라 1칸씩 올라가자 시간 복잡도 = O(N) => 어떻게 더 빠르게 찾을 수 있을까? 1칸씩 올라가는 것이 아닌 2^K씩 올라가자 => 시간 복잡도 = O(logN) 이때 다른 수도 아닌 2^K인 이유는??? 모든 수는 이진수로 나타낼 수 있기 때문에 parent[0][V] = 정점 V의 1(=2^0)번째 부모 parent[1][V] = 정점 V의 2(=2^1)번째 부모 ★ = 정점 V의 1번째 부모의 1번째 부모 ★ => parent[1][V] = parent[0][ parent[0][V] ] ★★ parent[K][V] = p..