1. 두 노드 a와 b에 대해, 서로 높이가 다르다면 높이를 맞추어줌.
2. 2의 거듭제곱 꼴로 높이를 낮추다가 공통 조상이 없어지는 곳으로 이동.
int lca(int a, int b, int K) { if (a == b) return a; //a = b // LCA는 a나 b보다 최소 높이 1보다 위에 있음. for (int i = K; i >= 0; i--) { if (parent[i][a] != parent[i][b]) return lca(parent[i][a], parent[i][b], i); //분기되는 최초의 지점으로 이동 } return parent[0][a]; // LCA는 바로 위의 조상. }
3. a와 b가 같아지거나 LCA를 찾기 이전까지 계속 '2.'를 반복.
'Problem Solving > Algorithm' 카테고리의 다른 글
Shortest Path Faster Algorithm (0) | 2016.07.28 |
---|---|
Divide & Conquer Optimization in DP (3) | 2016.06.12 |
Smallest Enclosing Circle/Sphere Problem (0) | 2016.02.17 |
Prüfer Sequence (0) | 2015.12.29 |
Aho-Corasick Algorithm (0) | 2015.09.27 |
댓글