본문 바로가기
Problem Solving/Algorithm

Lowest Common Ancestor(최소 공통 조상)

by hongjun7 2016. 3. 31.

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

댓글