코딩테스트에서 나오는 문제 중 하나인 LCS 구하기에 대해 공부해 보았다. 이 글의 내용은 Do it! 알고리즘 코딩테스트를 참고하였다. 최소 공통 조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라고면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 '최소 공통 조상' LCA(Lowest common ancestor) 이라고 한다. 최소 공통조상을 구하는 방법은 2가지가 있다. 일반적으로 구하는 방법과 빠르게 구하는 방법이다. 일반적으로 구하는 방법은 Depth를 하나씩 거슬러 올라가야 해서 모든 Depth를 탐색해야 할 수 도있다. 그래서 시간 복잡도가 크다. 하지만 빠르게 구하는 방법은 2의 K승 씩 올라가서 비교하면서 빠르게 구할 ..
