알고리즘 공부방

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번 종류의 쿼리가 하나..

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

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개의 명제로 바꾸었다. 항의 개수가..

SCC란, 방향 그래프에서 정의되는 개념으로, 한 SCC 내부에서 임의의 정점 u, v를 잡았을 때, u에서 v가 도달 가능한 컴포넌트를 의미한다. 한 그래프에는 여러개의 SCC가 존재할 수 있고, 이러한 SCC들을 분리해 내고 그 SCC들을 하나의 정점처럼 합쳐 주면 압축된 새로운 그래프를 얻을 수 있다. 이 그래프는 무조건 DAG 이고, 이를 이용하여 많은 문제들을 풀수 있다. ( 압축된 정점 들 간의 사이클이 존재하면 임의의 한 압축정점에서 다른 정점으로 양방향경로가 존재하니, 그 압축정점들 또한 하나의 SCC로 뭉쳐져야 한다. ) SCC는 $O(N+M)$ 안에 추출할 수 있고, Tarjan과 Kosaraju 두 방법이 있다. 1. Tarjan's Algorithm 타잔의 알고리즘은 기본적으로 그래..