분류 전체보기 (134) 썸네일형 리스트형 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 Com.. 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.. 163. GCD Segment Tree 연속된 원소들의 최대공약수를 빠르게 구하는 GCD 세그먼트 트리(GCD Segment Tree)에 대해 알아본다. 이 세그먼트 트리의 구성 방법은 간단하다. 리프 노드에 수열의 값들을 저장하고 부모 노드에 양 자식 노드에 저장된 값의 최대공약수를 저장하는 것이다. 다음과 같은 수열이 있다고 할 때, $$a = [48, 32, 24, 36, 18, 30, 20]$$ 이 수열을 GCD 세그먼트 트리로 표현하면 다음과 같다. 리프 노드가 빌 경우 $0$으로 채우면 된다. $x \ne 0$일 때 $\gcd(x, 0) = |x|$이므로 $20$과 $0$의 부모 노드에는 $20$이 저장된다. 또한 $\gcd(0, 0)$은 정의되지 않지만 일반적으로 그러는 것처럼 $0$으로 간주하면 된다. 이제 이 세그먼트 트리를 .. 162. Segment Tree with Lazy Propagation 다음과 같은 쿼리를 처리하는 문제를 생각해 보자. $1\ x\ y\ k$: $x$번째 수부터 $y$번째 수까지에 $k$를 더한다. $2\ x\ y$: $x$번째 수부터 $y$번째 수까지의 합을 출력한다. 만약 세그먼트 트리를 이용해서 이 쿼리를 처리하려고 한다면 $1$번 쿼리를 처리할 때 원소의 값을 바꾸는 작업을 $y - x + 1$번 실행해야 하고, 수의 개수가 $n$이라면 이 작업에는 $(y - x + 1) \lg n$만큼의 시간이 걸린다. 즉 이 시간은 바꿔야 하는 구간의 크기에 영향을 받는다. 만약 $x = 1, y = n$이라면 $1$번 쿼리 하나를 처리하는 데 $n \lg n$만큼의 시간이 걸릴 것이고 이런 쿼리가 $m$개 있다면 $nm \lg n$만큼의 시간이 걸리게 된다. 이런 시간복잡도.. 이전 1 2 3 4 ··· 17 다음
