백준 - 3584 가장 가까운 공통 조상
문제 링크입니다 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 문제 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상� www.acmicpc.net 시간 복잡도가 O(N)인 방법이다. RMQ로 구현하면 O(logN)으로 구현할 수 있다. 다음 문제들에서는 RMQ로 풀어봐야겠다. #include #include using namespace std; int T, N; vector adj; vector parent; vector depth; void dfs(int here, i..
알고리즘/백준(BOJ)
2020. 7. 21. 14:45