반응형 LCA1 백준 3584번 가장 가까운 공통 조상 - C++ 풀이 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 1. O(N)의 LCA 알고리즘을 사용하여 구한다. 단순한 LCA(Lowest Common Ancestor) 구하기 문제이다. N = 10,000 밖에 되지 않기 때문에 희소 테이블을 사용하지 않는 O(N)의 LCA로도 충분하다. #include #include #include using namespace std; const int MAX = 10'001; int N; int depth[MAX], parent[MAX]; vector children[MAX]; void dfs(int curr) { for (auto child: children[curr]) { depth[child] = depth[curr] + 1; dfs(child); } } int NC.. 2023. 8. 21. 이전 1 다음 반응형
