LCA Algorithm

LCA (Lowest Common Ancestor) 알고리즘

: 최소 공통 조상을 찾는 알고리즘

  즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘

 

Segment Tree를 사용한 방법, DP를 사용한 방법이 존재하는데 DP 사용법에 대해서 공부하였다.

 

출처 : https://www.crocus.co.kr/660

9와 6의 최소 공통 조상 : 2

4와 10의 최소 공통 조상 : 8

2와 15의 최소 공통 조상 : 1

 

 

 

 

• LCA 접근법

최소 공통 조상 찾는 방법

: 각 노드에서 부모를 타고 올라가서 같은 부모를 찾는다.

  이때, 양 노드의 레벨이 같아야 함.

 

=> 각 노드의 부모와 레벨을 알아야 하고, 트리가 있어야 함

 

 

각 노드의 부모 노드, 레벨 저장하는 법

=> DFS 사용

    재귀를 한 번씩 돌 때 마다 레벨 += 1, 부모 노드 또한 저장 가능.

 

 

ex) 6과 14의 공통 조상 구하기.

노드	레벨	부모노드
6	6	13
14	4	12

6의 레벨이 더 크므로, 노드 6을 노드 6의 부모 노드로 바꿔준다.

 

 

노드	레벨	부모노드
13	5	2
14	4	12

13의 레벨이 더 크므로, 노드 13을 노드 13의 부모 노드로 바꿔준다.

 

 

노드	레벨	부모노드
2	4	12
14	4	12

2와 14의 부모 노드가 12로 같다.

if 부모 노드가 다르다면, 부모 노드가 같을 때까지 양 노드를 부모 노드로 바꿔준다.

 

 

 

 

 

 

참고 : https://velog.io/@lre12/LCA-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Lowest-Common-Ancestor

https://www.crocus.co.kr/660