Algorithm/I. Data Structures & Advanced Algorithms (15) 썸네일형 리스트형 186. Heavy-Light Decomposition 헤비-라이트 분할(Heavy-Light Decomposition, HLD)는 트리에서 경로와 관련된 다양한 쿼리를 처리하는 테크닉이다. 트리에서 다음과 같은 쿼리를 처리하는 문제를 생각해 보자.$1\ i\ c$: $i$번째 간선의 가중치를 $c$로 바꾼다.$2\ x\ y$: 정점 $x$와 $y$ 사이의 최단 경로가 포함하는 간선들의 가중치의 합을 출력한다.정점이 $n$개인 트리에서 두 정점 사의의 최단 경로는 최대 $(n - 1)$개의 간선을 포함하므로 경로상의 간선을 하나씩 보는 방법은 당연히 너무 느리다. 이 문제점을 해결하기 위해 HLD는 간선을 그룹으로 묶은 다음 그룹을 한 번에 처리할 수 있게 한다. 이때 경로가 너무 많은 그룹을 지나면 간선을 그룹으로 묶는 의미가 없어지므로 어떤 경로를 선택하.. 184. Continuous Sum Segment Tree DP로 해결할 수 있는 문제 중 수열에서 최대 연속합을 구하는 문제가 있다. 이전에 소개한 적이 없으므로 여기서 소개를 하자면 다음과 같다. 아래 문제를 보자. BOJ 1912. 연속합 (Silver II) $n$개의 수가 주어지고 그것을 각각 $a_1, a_2, \ldots, a_n$이라고 했을 때 두 인덱스 $i$와 $j$를 잘 정해서 $a_i + a_{i + 1} + \ldots + a_{j - 1} + a_j$가 최대가 되도록 해야 한다. 세 번째 예제에서 볼 수 있듯이 모든 수가 음수인 경우에도 최소 하나의 수를 골라야 한다. 이 문제를 DP로 풀기 위해 식을 세워 보자. $j$가 $1$인 경우부터 $n$인 경우까지 각각에 대해 해당 조건에서의 최대 연속합 $m_j$를 구하고 거기서 가장 큰 .. 170. Mo's Algorithm 이번에는 제곱근 분할법을 수열에 적용하는 방법을 알아보자. 모스 알고리즘(Mo's Algorithm)은 제곱근 분할법을 이용하여 세그먼트 트리 등의 자료 구조로 처리하기 어려운 쿼리를 처리하는 방법이다. 제곱근 분할법을 수 자체에 적용할 때는 제곱근 이하와 이상, 두 부분을 따로 다루었는데 제곱근 분할법을 길이가 $n$인 수열에 적용하면 $\sqrt{n}$ 정도의 길이를 갖는 $\sqrt{n}$개의 구간을 기준으로 접근하게 된다는 차이점이 있다는 것은 제곱근 분할법을 수에 적용하는 방법을 소개할 때도 언급했다. 그러면 모스 알고리즘의 작동 방법을 알아보자. 여기서 $\sqrt{n}$은 전부 근삿값이며 적당히 가까운 정수를 사용하면 된다. 또한 처리하는 쿼리들은 구간 $[l, r]$로 나타낼 수 있으며 한.. 169. Square Root Decomposition 적당한 분할을 통해서 시간복잡도를 최적화하는 또 다른 방법을 알아본다. 제곱근 분할법(평방 분할, Square Root Decomposition)은 큰 구간을 구간 크기의 제곱근을 기준으로 분할한 다음 연산을 빠르게 처리하는 방법이다. 여기서 큰 구간은 크게 두 가지 형태로 나타나는데, 한 가지는 수열이고 다른 한 가지는 수 자체이다. 구간의 형태에 따라 제곱근 분할법을 적용하는 방식도 다르게 나타난다. 길이가 $n$인 수열에 제곱근 분할법을 적용할 때는 보통 이것을 $\sqrt{n}$ 정도의 길이를 갖는 구간 $\sqrt{n}$개로 분할한 다음 원하는 연산을 처리하는 방식이 주로 사용되지만, 수 자체에 제곱근 분할법을 적용할 때는 수를 $\sqrt{n}$ 이하와 $\sqrt{n}$ 이상의 두 그룹으로 .. 168. Merge Sort Tree 이전에 병합 정렬이라는 정렬 방법을 소개한 적이 있다. 이걸 응용해서 자료구조로 써먹는 방법을 알아본다. 머지 소트 트리(Merge Sort Tree)는 병합 정렬 과정을 세그먼트 트리에 저장한 자료 구조이다. 앞서 병합 정렬의 시간복잡도와 공간복잡도가 $\Theta(n \lg n)$이라고 했는데, 정렬 과정에서 생긴 데이터를 버리지 않고 그대로 저장하면 머지 소트 트리를 만들 수 있다. 즉 $\Theta(n \lg n)$의 시간복잡도로 $\Theta(n \lg n)$의 메모리를 사용하는 머지 소트 트리를 만들 수 있다. $$[6, 3, 5, 7, 1, 4, 2]$$ 이 수열로 머지 소트 트리를 만들어 보자. 구간을 분할하는 부분은 별로 중요하지 않기 때문에 합치고 정렬하는 부분만 트리로 만들면 된다. .. 167. Lowest Common Ancestor 다음과 같은 트리가 있다고 가정해 보자.$9$번 정점이 루트라고 하면 다른 정점들의 부모와 조상들을 결정할 수 있다. 예를 들어 $3$번 정점의 부모는 $9$번 정점이고, $8$번 정점의 조상은 $5$번 정점과 $9$번 정점이 된다. 이제 여러 정점의 조상을 생각해 보자. $7$번 정점의 조상은 $4$번, $3$번, $9$번 정점이고 $6$번 정점의 조상은 $3$번, $9$번 정점이다. 여기서 $3$번과 $9$번 정점은 $6$번 정점의 조상이면서 $7$번 정점의 조상이다. 이런 정점들을 $7$번 정점과 $6$번 정점의 공통 조상(Common Ancestor)이라고 한다. 또한 이중 깊이가 가장 깊은 정점은 $3$번 정점인데, 이 정점을 $7$번 정점과 $6$번 정점의 최소 공통 조상(Lowest Comm.. 166. Euler Tour Technique 지금까지 수열에서 구간 업데이트와 구간 합을 구하기 위해 세그먼트 트리를 사용하였다. 이번에는 이것을 일반적인 트리 구조에 적용해 볼 것이다. 오일러 투어 테크닉(오일러 경로 테크닉, Euler Tour Technique, ETT)은 세그먼트 트리에서 일자형 구조에 사용한 기술을 트리 구조에 적용할 때 사용되는 방법으로 다음과 같은 쿼리들을 처리할 수 있게 해 준다. 노드마다 값을 하나씩 가진다고 하자. 노드 $v$에 할당된 값을 변경한다. 노드 $v$를 루트로 하는 서브트리의 각 노드에 할당된 값을 변경한다. 노드 $v$에 할당된 값을 출력한다. 노드 $v$를 루트로 하는 서브트리의 각 노드에 할당된 값의 합(최대, 최소 등 다양하게 변경할 수 있음)을 출력한다. 즉 노드 쿼리나 서브트리 쿼리를 처리할.. 165. Sparse Table 희소 테이블(Sparse Table)은 정점마다 나가는 간선이 하나씩 존재하는 유향 그래프에서 사용할 수 있는 자료 구조로 어떤 정점에서 간선을 따라 여러 번 이동했을 때 어떤 정점에 도착하는지를 빠르게 구할 수 있다. 가끔씩 희소 배열(Sparse Array)이라고 표현하기도 하지만 이 단어는 다른 뜻이 많아 혼동하기 쉬워서 잘 쓰이지 않는다. 다음과 같은 그래프가 있을 때 정점 $\text{D}$에서 간선을 따라 $4$번 이동하면 정점 $\text{C}$에 도착한다. 각 정점에서 간선을 따라 이동했을 때 도착하는 정점을 이동 횟수에 따라 표로 나타내면 다음과 같다. $0$ $\text{A}$ $\text{B}$ $\text{C}$ $\text{D}$ $\text{E}$ $\text{F}$ $\text.. 이전 1 2 다음
