알고리즘 공부방

https://apio2019.ru/https://oj.uz/problems/source/389https://koosaga.com/232 내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...이번 년도의 문..

https://koosaga.com/121 https://codeforces.com/gym/100551/problem/A https://www.acmicpc.net/problem/16911 cp-algorithms.com/data_structures/deleting_in_log_n.html 1. 간선 추가 2. 간선 삭제 3. 정점 u, v가 연결되어 있는지 판별 이 문제를 online 으로 처리하는 것은 매우 어려운 문제이다. 따라서 Offline 으로 분할정복을 활용하여 해결하자. 가장 먼저, 각 간선의 생존시간을 시간축에 표시하면 어떠한 구간이 된다. 이 구간을 segment tree에 $logN$ 개의 노드에 업데이트 된 것이라고 생각하고, 이후 segment tree의 노드들을 전위순회하면서 u..

https://www.acmicpc.net/workbook/view/914 수열과 쿼리 1, 3 https://www.acmicpc.net/problem/13537 https://www.acmicpc.net/problem/13544 Merge Sort Tree를 이용하여 해결할 수 있다. 주어진 구간의 $logN$ 개의 노드들에 대하여 K 이상의 수들을 이분탐색하면 $O(NlogN+Qlog^2{N})$ 안에 해결할 수 있다. 수열과 쿼리 5 https://www.acmicpc.net/problem/13547 Mo's algorithm 으로 해결할 수 있다. 특정 구간에 오른쪽, 왼쪽에서 삽입, 삭제하는 시간이 O(T) 라 한다면 전체 시간복잡도는 $O(N^{1.5}T)$ 안에 해결할 수 있다. 서로 다른..

$N*M$ 크기의 격자에 다음과 같은 두 쿼리가 주어진다. 1. 한 칸의 값을 바꾼다 2. (x1, y1) ~ (x2, y2) 의 합, 최댓값, 최솟값 등을 구한다. 이 문제는 1차원의 문제가 segment tree 를 이용하면 풀리듯이 2D Segment Tree 를 이용하면 풀 수 있다. 하지만 2D Segment Tree 를 사용하면 공간 복잡도가 다이나믹 세그 + 메모리 제한이 빡빡할 경우에는 경로 압축까지 해 주어야 $O(NlogN)$ 이 나오기 때문에 시간, 공간의 측면에서 모두 비효율 적이다. 하지만 이 문제가 오프라인으로 풀 수 있다면 2D Segment Tree 를 구현하지 않아도 더 빠르게 풀 수 있다. 바로 분할 정복을 이용한 것이다. 시간의 흐름에 따라 1, 2번 종류의 쿼리가 하나..