코딩테스트/백준
[코테] 백준 11438번 : LCA 2 (java)
https://www.acmicpc.net/problem/11438알고리즘 분류 : 자료 구조, 트리, 최소 공통 조상, 희소 배열❓문제🔅해석순서input된 값을 adjacent list(양방향 간선)에 넣는다.BFS로 트리 탐색bfs로 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록한다. 희소 테이블(Sparse Table) 구성각 노드에 대해 2^k번째 부모를 미리 계산한다. 이 테이블을 이용하면, 두 노드의 깊이를 맞춘 후, 공통 조상을 빠르게 찾을 수 있다.Find LCA항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swapa, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)2에서 depth를 맞추었는데 a와 b가 같다면 lca를 ..
