LCA를 O(logN)에 구하기 - Sparse Table

코테 수준에서 이거? 알 필요 없습니다. 근데 백준 11437번: LCA를 멍청한 구현으로 풀고 나니 살짝 허무해서, 개념을 공부하고 문제를 좀 풀어봤습니다.

 

개념

한 마디로 'Sparse Table'이라는 자료 구조에 각 노드의 (2의 제곱번째) 조상'들'을 저장하여 (처리 과정 O(NlogN)), 이후 LCA를 O(logN)에 구할 수 있도록 하는 방법입니다. Q번의 LCA를 찾는 과정을 naive한 풀이는 O(NQ)의 시간 복잡도 내에 수행하나, sparse table을 이용하면 O((N+Q)logN) 시간 복잡도 내에 수행할 수 있습니다.

parent[cur][i] = parent[parent[cur][i-1]][i-1]의 의미를 잘 알아두면 나중 구현할 때 기억하기 좋을 듯합니다.

자세한 설명은 라이 블로그를 참고하세요.

 

문제

백준 11438번: LCA 2

배운 거 그대로 쓰면 됩니다.

 

백준 8012번: 한동이는 영업사원!

배운 거 그대로 쓰면 됩니다.

 

백준 1761번: 정점들의 거리

두 정점 u, v의 lca가 w라면, 두 노드 사이의 거리는 dist[u] + dist[v] - 2*dist[w]가 됩니다.

 

백준 3176번: 도로 네트워크

다른 sparse table 2개를 더 만들어, 구간에서의 최댓값/최솟값을 저장해주면 됩니다.

 

백준 13511번: 트리와 쿼리 2

1) 비용 출력 -> 1761번이랑 동일합니다.

2) k번째 정점 출력 -> 정점 u, v 사이에 있는 정점의 수를 구한 후, u에서 올라가서 찾을 수 있는 경우와 v에서 올라가서 찾을 수 있는 경우를 나누어 처리합니다.