SWEA 1855 LCA알고리즘을 사용하여 최소공통 조상을 구하는 알고리즘이다. 처음에 LCA알고리즘을 몰라서 한칸씩 부모를 타고 올라가 시간 초과가 났던 문제이다. LCA란? 아이디어를 간단하게 요약하면 다음과 같다 >* 트리 구조체에서 자신의 2의 거듭제곱번째 조상을 dp배열에 저장한다. > > * 특정한 두 노드의 최소 공통 조상을 찾을 때 dp배열을 활용하여 1칸->2칸->4칸 ...씩 타고 올라간다. 일단 dp배열을 생성하는 코드는 다음과 같다 i 의 $$2^j$$번째 조상은 i의 $$2^j-1$$번째 조상의 $$2^j-1$$번째 조상이다 라고 이해하면 된다. 영준이가 방문할 노드는 BFS를 따라가기 때문에 Queue에 방문 순서를 넣어 이를 구현하였다