알고리즘 코딩테스트 핵심이론 강의 - 최소공통조상(LCA) 기본편

https://www.youtube.com/watch?v=qUYkV2F1R-k

📌 최소공통조상(LCA)

• 트리 그래프에서 임의의 두 노드를 선택했을 떄 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음으로 공통으로 만나게되는 부모노드를 말함

 

◾ 일반적인 최소공통조상 구하기

• 트리의 높이가 크지 않을 때 사용

 

• 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장

• 탐색은 DFS 또는 BFS를 이용해 수행
  → 트리라는 특징 때문에 바로 직전 탐색 노드가 부모노드가 되며, 탐색을하면서 depth 구하기 가능
  
  
• 선택된 두 노드의 깊이가 다를 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 같은 깊이로 맞춘다. 이때, 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료
• 노드의 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복
  
  

→ 부모노드 찾아서 올라가기

 

• 일반적인 최소공통조상 찾기 방법은 트리의 높이가 커질 경우 시간 제약 문제 발생