LCA란? LCA는 Lowest Common Ancestor의 약자로 해석하면, 최소 공통 조상(가장 낮은 공통 조상)이라는 뜻을 가지고 있다. '조상'이기 때문에 트리에서 사용하며, 다양한 특징을 가지고 있어 트리 문제를 해결할때 기초로 잘 사용되어진다. 트리에서는 조상이 존재한다. 어떤 노드의 부모, 부모의 부모, 부모의 부모의 부모해서 루트까지의 모든 노드를 조상노드라고 하며, 공통 조상은 2개의 노드들에 대하여 어떤 노드가 그 두 노드의 공통적으로 조상일때를 말한다. 그러한 공통 조상들 중에서 가장 낮은 (깊이가 깊은, 처음 만나는) 공통조상이 최소 공통 조상 즉 LCA가 된다. 위와 같은 트리가 있다고 할 때 LCA(9,10)=4, LCA(9,11)=2, LCA(5,9)=2, LCA(12,13)..