알고리즘 공부방

2D Segment Tree는 y축에 Segment Tree 한개, x축에 Segment Tree 한개를 이용하여 이차원 좌표상의 한 점 업데이트 및 구간 연산 쿼리를 빠르게 처리할 수 있는 자료구조이다. y축 Segment Tree는 각 노드마다 x축 Segment Tree 를 하나씩 갖고 있으며, 정확히는 구간 [yl, yr]을 담당하고 있을 때, 각 노드가 [yl, yr][x, x] 를 노드로 갖는 x축 Segment Tree 를 의미한다. 그냥 구현하면 공간 복잡도가 $O(N^2)$ 이니, Dynamic Segment Tree로 X축, Y축을 모두 구현할 필요가 있다. Dynamic Segment Tree를 사용하다 보니, Pointer 을 사용한 구현과 벡터 기반의 구현 두가지가 모두 존재한다...

머지 소트 트리란, 말 그대로 머지 소트의 과정을 그대로 저장하여 만들어논 트리이다. 예를 들어 최대 부분합 문제를 분할정복으로 푼 후, 그 과정을 세그먼트 트리로 옮겨 놓을 수 있듯이, 머지 소트가 일어나는 과정을 각각 하나의 노드로 만들어 저장하는 것이다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1e5; int N, Q, A[MAXN+10]; vector tree[4*MAXN+10]; void combine(vector &a, vector &b, vector &c) { int pa=0, pb=0; while(pa

Heavy Light Decomposition 은 트리에서 segment tree 등의 자료 구조를 활용할 수 있도록 만드는 방법이다. 1차원에서 업데이트, 쿼리를 처리하는 문제는 segment tree 등의 자료구조를 활용하여 풀 수 있다. 하지만 트리에서는 이 과정이 어렵기 때문에 트리를 몇개의 체인으로 쪼갠 후 각 체인에서 segment tree 등을 사용하는 것이다. 하지만 만약 이 체인의 수가 많아지면 그만큼 시간이 많이 걸리기 때문에 체인의 개수를 적당히 적게 만드는 방법이 필요하다. HLD 는 다음과 같이 트리에서 각 노드에서 자식들 중 가장 서브트리가 큰 서브트리까지의 간선을 "무거운 간선"으로 분류한다.이렇게 해서 "무거운 간선"들로만 묶이면 체인들 몇개로 트리가 분해되게 된다. 이때 가..

Convex Hull Trick은 DP의 시간 복잡도를 획기적으로 줄일 수 있는 방법으로, DP optimization의 세가지 종류 중 하나이다. CHT조아 $dp(i) = min_{j

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

문제 https://codeforces.com/contest/1187/problem/E 트리에서 어떤 노드를 시작으로 선택한 노드들과 인접한 노드들을 골라 검정색으로 칠하는 과정을 계속 반복한다. 이때 노드 하나를 선택할 때 아직 색칠되지 않은 컴포넌트의 크기만큼의 점수를 얻을 때, 점수의 최댓값을 구하는 문제이다. 풀이 가장 먼저, 처음에 선택하는 노드를 하나 정해놓고 생각해보자. 다음에 선택하는 노드는 그 노드와 연결되어 있는 점이어야 하고, 다음에 선택할 점들을 어떤 순서로 골라도 상관이 없다. 이를 이용하면, 다음을 알 수 있다. 루트 하나를 고정시켜 놓은 트리에서, 각 노드마다 서브트리의 크기를 구하면 그 서브트리 크기의 합이 바로 답이 된다. 이는 트리 DP를 이용하여 구할 수 있다. dp[v..

https://contests.ioi-jp.org/open-2018/index.htmlhttps://oj.uz/problems/source/351 역시 JOIOC는 어렵다. 문제 하나하나가 다 좋은 문제이고, 많이 생각할 수 있게 해주는 문제들인 것 같다.4일동안 1, 4번을 풀었고, 2번은 부분점수, 3번은 풀지 못하였다.Heavy Light Decomposition을 응용한 DP 최적화, Sqrt Decomposition 등 아직 내가 익숙하지 않은 개념들이 많이 이용되어서 더 어렵게 느껴진 것 같다. 나중에 이런 개념들을 잘 익힌 후에 꼭 다시 풀어봐야 할 문제들이다. 4. xylophone 순열이 하나 있고, 물어볼 수 있는 쿼리는 오직 어떤 구간 내의 최대값-최솟값만 물어볼 수 있을 때 2N 번..

LCA란, Lowest Common Ancestor 로, 트리에서의 최소 공통 조상이다. 공통 조상은 두 노드에 대해, 두 노드 모두의 자손인 조상 노드들을 의미하며, 그중 깊이가 최대인 것, 즉 가장 아래쪽에 위치한 노드를 두 노드에 대한 최소 공통 조상 이라 한다. 기본적인 아이디어는 두 노드에 대해서 1. 두 노드의 깊이가 같도록 하나의 노드를 올려준 후, 2. 두 노드가 같아질 때까지 올려준다. 이 연산을 그냥 실행하면, 최악의 경우에 $O(N)$의 시간이 걸릴 수 있다. 이는 Sparse Table 을 사용하여 LCA 연산을 $O(logN)$에 처리할 수 있다. 가장 먼저 dfs 한번을 돌면서 각 노드들의 깊이와, 노드들의 부모를 sparse table 안에 저장한다. 다음, $par[i][j]..

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..

2-SAT 문제는 다음과 같다. (a or b) 꼴의 식 여러 개를 and 연산으로 연립한 것이다. 이때 각 a, b, c 변수는 true, false 를 값으로 하는 변수이다. 각 변수에는 not 을 붙일 수 있다. 이 문제는 변수들 간의 방향 그래프로 모델링 한 후, SCC를 사용하여 해를 구할 수 있다. 첫 번째로, 각 항의 (a or b)는 모두 true 가 되어야 한다. 이제 하나의 항만 생각해 보자. (a or b) 가 성립하기 위해서는 a가 false이면 b가 true / b가 false이면 a가 true 여야 한다. 이를 명제로 표현하면 !a -> b , !b -> a 이다. 이 명제들이 모두 성립한다면 (a or b) 가 성립한다. 이제, 모든 항들을 2개의 명제로 바꾸었다. 항의 개수가..