devbelly

문제 www.acmicpc.net/problem/18783 알고리즘 Sparse table 풀이 소들이 $M$ step을 $K$번 반복했을 때, 최종적인 소의 배치를 구하는 문제입니다. $M$과 $K$의 범위가 크므로 시간복잡도 $O(MK)$ 로는 해결할 수 없습니다. 대신 $K$을 비트로 표현하여 켜진 비트에 대한 다음의 상태를 관리할 수 있는 sparse table을 통해 $K$를 $logK$로 줄일 수 있습니다. 모든 배열의 $K$이후의 상태를 물어보기 때문에 sparse배열을 두개만 만들어 메모리를 절약할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >>..

문제 www.acmicpc.net/problem/11438 알고리즘 sparse table 풀이 LCA를 빠르게 처리하는 문제입니다. LCA를 구하는 과정은 두 단계로 나뉩니다. 첫 번째는 두 정점 간의 깊이를 일치시키고 만일 이때 정점이 일치하지 않다면 각자의 $2^i$ 위의 정점을 살펴보며 다르다면 트리에서 올라가면 됩니다. 높이가 일치한 후 $2^i$ 위의 정점이 다르다면 올라갈 여지가 남았다는 뜻이기 때문입니다. LCA쿼리당 요구하는 시간복잡도는 $O(logN)$입니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1; i = 0; --i) { if ((dep[u] - dep[v]) ..