oVeron

헤비 라이트 분해(Heavy-Light Decomposition, HLD) : 트리를 여러 체인(chain)으로 나눠 트리의 경로에 대한 질의를 편리하게 처리하게 해 주는 알고리즘. 트리의 두 노드 간의 거리, 합, 최댓값과 최솟값 등 경로에 관한 질의를 세그먼트 트리 등을 사용하여 \(O(logN), O((logN)^2)\) 등에 처리할 수 있다. 우선 트리를 여러 개의 체인으로 나눈다. 체인(chain)이란 쉽게 말해 트리의 부분 경로를 의미한다. 루트 노드부터 시작해 자식 노드를 하나의 체인으로 묶을 때, 서브트리의 크기가 가장 큰 자식을 루트 노드와 같은 체인으로 묶고, 다른 자식은 새로운 체인의 시작점(head)으로 삼는다. 이때 현재 노드와 자식 노드 간의 간선을 heavy 간선, 그 외 간선..

알고리즘/algorithm 2025. 8. 28. 18:58

가장 가까운 두 점 간 거리https://www.acmicpc.net/problem/2261 1. 점들의 개수를 y축에 평행한 직선을 기준으로 절반으로 나누어 왼쪽 구간과 오른쪽 구간으로 나눈다. 우선 왼쪽 구간, 오른쪽 구간에서의 최단 거리를 구한 이후, 두 구간을 합쳐 새로운 답을 구할 것이다. 2. 왼쪽 구간과 오른쪽 구간의 최단 거리를 구했다면, 두 거리 중 더 짧은 거리가 답의 후보가 될 수 있을 것이다. 이 거리를 \(d\)라 하자. 이제 왼쪽 구간의 점과 오른쪽 구간의 점을 이은 선분의 최단 거리를 구해야 하는데, 지금 우리가 구한 최단 거리가 \(d\)이므로 기준선으로부터 좌우로 \(d\)만큼 떨어진 점들만을 모은다. 3. 모은 점들을 y축 기준으로 오름차순 정렬한다. 이제 한 점씩 살..

알고리즘/algorithm 2025. 8. 26. 11:35

다각형의 넓이다각형의 점들이 CCW 순으로 주어진다 생각하자. 이 경우 신발끈 정리를 이용해 다각형의 넓이를 구할 수 있음이 알려져 있다.\[ A = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|, \quad x_{n+1}=x_1, \; y_{n+1}=y_1 \]위 공식은 \(\{0, 0\}, \{x_i, y_i\}, \{x_{i+1}, y_{i+1}\} \) 세 점으로 이루어진 삼각형의 면적을 전부 더한 것이다. 점들이 CCW 순으로 정렬되어 있기에 이들을 다 더한 값에 절댓값을 취하면 다각형의 면적을 구할 수 있다. https://www.acmicpc.net/problem/2166#include using namespace..

알고리즘/algorithm 2025. 8. 26. 08:42

컨벡스 헐 트릭(Convex Hull Trick, CHT) : 다음과 같은 dp 식에서 사용할 수 있는 dp 최적화 기법$$ dp[i] = \min_{j 위의 수식은 직선의 방정식으로 나타낼 수 있다. \(dp[i] = y, a_i = x, b_j = sl_j, dp[j] = ic_j\)라 표현하면 위 수식을 다음과 같이 쓸 수 있다.$$ y = \min_{j 이때 \(sl_j\)는 \(j\)번째 직선의 기울기, \(ic_j\)는 \(j\)번째 직선의 y절편을 의미한다. 따라서 \(dp[i]\)는 \(i\)보다 인덱스가 작은 \(i-1\)개의 직선들에 대하여, x값이 \(a_i\)일 때 y값의 최솟값을 의미한다. 위 수식을 그림으로 표현하면 위 사진과 같다. 굵은 실선은 x(\(a[i]\))값에 따른 y..

알고리즘/algorithm 2025. 8. 26. 00:19

모 알고리즘(Mo's) : 정적 배열에 대한 복잡한 구간 질의를 제곱근 분할법을 이용해 효율적으로 처리하는 알고리즘제곱근 분할법이란, 어떠한 배열의 크기를 \(N\)이라 할 때 이 배열을 \(\sqrt{N}\)개로 나누는 방식을 의미한다. 구간을 이런 방식으로 나눔으로써, 세그먼트 트리 등으로는 풀 수 없는 복잡한 구간 질의를 \(O(N\sqrt{N})\)의 시간복잡도로 해결할 수 있다. https://www.acmicpc.net/problem/13547정적 배열에서 주어진 구간에서의 서로 다른 수의 개수를 구해야 하는데, 세그먼트 트리로는 해결하기 어려워 보인다. Mo's를 이용해 이 문제를 해결해 보자. 우선 주어진 쿼리를 입력받는 대로 처리(온라인 쿼리)하지 말고, 쿼리를 정렬하여 답을 구한 다음 ..

알고리즘/algorithm 2025. 8. 25. 20:13

오일러 경로 테크닉(Euler Tour Technique, ETT) : 트리를 DFS 탐색한 순서를 배열에 저장하여, 트리의 서브트리 질의 또는 경로 질의를 배열의 구간 질의로 바꾸는 기법 https://www.acmicpc.net/problem/16404이 문제의 예시 입력으로 주어진 그래프를 ETT로 나타내면 아래 그림과 같다. \(DFS_cnt\)는 DFS를 통해 어떠한 정점을 몇 번째로 방문했는지를 나타내는 수이다. \(in[i], out[i]\)은 정점 \(i\)에 처음 방문했을 때의 \(DFS_cnt\), 정점 \(i\)의 서브트리를 전부 순회하고 나온 후의 \(DFS_cnt\)를 나타낸다. \(in[i], out[i]\)를 통해 정점 \(i\)의 서브트리의 구간을 배열로 나타낼 수 있고, ..

알고리즘/algorithm 2025. 8. 22. 13:58

두 명의 플레이어가 다음과 같은 규칙을 갖는 게임을 한다고 하자.1. 두 플레이어가 번갈아가며 게임을 진행한다.2. 게임은 여러 '상태'로 구성되어 있으며, 상태 간 이동하는 방법은 플레이어의 차례와 무관하다.3. 어떠한 플레이어가 움직일 수 없을 경우, 게임을 종료한다.4. 끝나지 않는 게임은 없다.5. 각 플레이어는 게임의 상태, 가능한 움직임에 대한 모든 정보를 가지고 있으며, 게임 내에 무작위적인 요소는 없다. 길게 풀어서 썼지만, 두 사람이 번갈아가며 하는 게임을 하나 생각하면 된다. 대표적인 예시로 '베스킨라벤스 31'이 있다. 두 플레이어가 번갈아가며 하며, 게임이 여러 상태(말할 수 있는 숫자 하나하나가 게임의 상태를 나타낸다)로 구성되어 있고, 상태 간 이동 방법(1, 2, 3개의 숫자 ..

알고리즘/algorithm 2025. 8. 21. 18:52

최대 유량(Maximum Flow) : 그래프(네트워크)의 한 출발점(source)에서 도착점(sink)까지 보낼 수 있는 유량(flow)의 최대치그래프의 각 간선마다 용량(capacity)이 존재한다 생각해보자. 간선의 용량이란 간선에 흐를 수 있는 유량의 최대치를 의미한다. 예를 들어 어떠한 간선의 용량이 10이라면, 우리는 이 간선에 0~10만큼의 유량을 흐르게 할 수 있다. 각 간선에 용량이 존재하는 그래프에서 흐를 수 있는 최대 유량을 구하는 문제를 최대 유량 문제 또는 네트워크 유량 문제라 부른다. 최대 유량을 구하는 방법은 다음과 같다.1. 그래프 탐색을 통해 source부터 sink까지 유량을 흘릴 간선을 찾는다.2. 그 간선들 중 용량이 가장 작은 간선을 택하여, 해당 간선의 용량만큼 찾..

알고리즘/algorithm 2025. 8. 20. 19:36