-
[BOJ] 11438 : LCA2
11438 : LCA2 풀이 이번엔 naive가 아닌 풀이! 이전의 naive한 풀이에서, 우리는 최악의 경우에 n번의 노드를 하나씩하나씩 올라가야했다. 하지만 이를 log(n)으로 줄일 수 있다! pnt[i][j] = i번 노드의 2^j번째 조상으로 두고 풀면 된다. 트리의 깊이를 구할 때 2^j번째 조상을 구해두자. tmp = anc[i][j-1]일 때, anc[i][j]는 anc[tmp][j-1]과 같다. 즉, i의 2^j번째 조상은 2^(j-1)번째 조상의 2^(j-1)번째 조상과 같다는 의미이다. i의 2^3=8번째 조상은 2^2=4번째 조상의 2^2=4번째 조상과 같다. naive한 코드에서 2^j를 도는 동작만 추가해주면 어렵지 않게(?) 훨씬 빠르게(!)...
-
[BOJ] 11437 : LCA
11437 : LCA 풀이 naive한 풀이! dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤, u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에 두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 5e4 + 3; int n, m; int dph[n_], pnt[n_]; vector<int> gph[n_]; inline void dfs(int now, int cnt) { dph[now] = cnt++; for (auto...