dh_0e

도로 네트워크 (백준 3176번) LCA 2(백준 11438번)처럼 희소 배열을 이용한 최소 공통 조상(Binary Lifting) 알고리즘을 활용한 문제. [PS] LCA 2 / C++ (백준 11438번)희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfdh-0e.tistory.com구현이 꽤 복잡하지만 설계를 잘 하고, LCA를 적절하게 구현하면 쉽게 풀 수 있다. #include#include#includeusing namespace std;vector> vec[100001];int depth[100001],..

LCA 2 (백준 11438번) 희소 배열(Sparse Table)을 사용해 LCA를 O($logn$)만에 구해야한다. 일반적으로 희소 배열을 사용하면 O(n)이 걸리기 때문에 Binary Lifting 방식으로 공통 조상을 찾는 과정이 필요하다. 풀이 과정1. 우선 dfs()함수로 트리를 만들며 각 node들의 parent 정보를 희소 배열에 저장하는데 이때, 희소 배열을 2차원으로 parent[i][j]=i번째 node에서 $2^j$번째 부모를 저장하는 방식으로 만들어준다. N 2. depth 배열을 만들어 각 node들의 깊이 또한 저장해준다. 주요 식은 다음과 같다.parent[i][j]=parent[parent[i][j-1]][j-1]; 3. 다음 입력받은 두 노드의 깊이를 맞춰준다. 이때, 2..