LCA Algorithm

Computer Science/Algorithm

leta 2021. 7. 30. 18:37

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

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

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

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

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

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

최소 공통 조상 찾는 방법

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

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

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

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

=> DFS 사용

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

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

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

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

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

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