Algorithm/I. Data Structures & Advanced Algorithms (15) 썸네일형 리스트형 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$만큼의 시간이 걸리게 된다. 이런 시간복잡도로는.. 161. 2D Segment Tree & 2D Fenwick Tree $2$D 세그먼트 트리($2$D Segment Tree)는 세그먼트 트리를 $2$차원으로 구성한 것이다. 즉 $1$차원 세그먼트 트리들이 여러 개 존재하고 여기서 같은 위치에 있는 노드들로 구성된 세그먼트 트리들이 추가로 존재하는 방식이다. 다음과 같이 $4 \times 4$ 크기의 테이블이 존재할 때 $2$차원 세그먼트 트리를 어떻게 구성하는지 알아보자.ABCDEFGHIJKLMNOP$1$차원 세그먼트 트리를 구현할 때 $1$차원 배열을 선언했다. 비슷하게 $2$차원 세그먼트 트리를 $2$차원 배열로 구현할 것이다. 그러면 첫 번째 인덱스를 행, 두 번째 인덱스를 열에 대응해서 각 노드가 어느 범위의 데이터를 저장할지 결정할 수 있다.더보기첫 번째 인덱스로 다음과 같이 행 범위를 지정한다.$a[1][]$.. 160. Segment Tree - kth 세그먼트 트리에서 $k$번째 원소를 빠르게 찾는 방법에 대해 알아본다.다음과 같은 쿼리가 $q$개 주어지는 문제를 생각해 보자.$1\ k$: 집합에 원소 $k$를 추가한다. $k$는 $1$ 이상 $n$ 이하의 정수 중 하나이다.$2\ k$: 집합에서 $k$번째로 작은 원소를 출력한다.이 문제를 해결하는 가장 간단한 방법은 $1$번 쿼리에서 추가되는 원소를 정렬된 집합에 끼워넣는 방법과 $2$번 쿼리마다 집합을 정렬하는 방법이지만 두 방법 모두 쿼리 하나를 처리하는 시간이 $\Omega(n)$이 돼서 전체 시간복잡도는 $\Omega(nq)$로 표기할 수 있다. 물론 $n$과 $q$가 크면 속도가 너무 느려진다.세그먼트 트리는 이 문제를 $\Theta(q \lg n)$에 해결하는 방법을 제공한다. 처음에 모.. 159. Fenwick Tree 세그먼트 트리의 변형 버전인 펜윅 트리(Fenwick Tree)에 대해 알아본다. 펜윅 트리는 세그먼트 트리의 구조를 응용하여 원소들의 값이 변할 수 있을 때 누적합을 빠르게 구할 수 있게 하는 자료 구조이다. 먼저 합 세그먼트 트리에서 누적합을 구할 때 어떤 노드들이 사용되는지 확인해 보자. 합 세그먼트 트리를 설명할 때 노드들에 위와 같이 번호를 매기는 것이 일반적이라고 했다. 여기서 앞쪽 $k$개 원소의 누적합을 구할 때 합에 포함되는 노드들의 번호를 나열하면 다음과 같다. $k=1$인 경우: $8$ $k=2$인 경우: $4$ $k=3$인 경우: $4$, $10$ $k=4$인 경우: $2$ $k=5$인 경우: $2$, $12$ $k=6$인 경우: $2$, $6$ $k=7$인 경우: $2$, $6$,.. 158. Segment Tree 알고리즘 문제를 풀 때 가장 자주 등장하는 자료 구조 중 하나인 세그먼트 트리(Segment Tree)에 대해 다룬다. 먼저 누적합을 다루면서 소개했던 구간 합 구하기 4 문제를 다시 보자. 수 $n$개가 주어졌을 때, $i$번째 수부터 $j$번째 수까지 합을 구하는 프로그램을 작성하시오. 이 문제에서 주어지는 쿼리는 아래와 같다. $i\ j$: $i$번째 수부터 $j$번째 수까지의 합을 출력한다. 수의 개수 $n$과 쿼리의 개수 $m$의 최댓값이 $10^5$이므로 누적합을 전부 구한 다음 각 쿼리를 $\Theta(1)$에 처리하면 $\Theta(n + m)$에 전체 문제를 해결할 수 있었다. 이제 쿼리를 하나 더 추가하자. $1\ x\ y$: $x$번째 수를 $y$로 바꾼다. $2\ x\ y$: $x$.. 157. Data Structures Intro 카테고리 I에서는 자료 구조와 고급 알고리즘에 대해 다룬다. 자료 구조(Data Structures, DS)는 자료를 효율적으로 저장, 관리, 조직할 수 있게 만들어 주는 구조를 의미한다. 문제를 풀기 위해 적절한 자료 구조를 선택하는 것은 빠르고 효율적인 알고리즘을 사용할 수 있게 하기 때문에 중요하다. 자료 구조와 함께 고급 알고리즘도 몇 개 다룬다. 주요 내용은 다음과 같다. 세그먼트 트리(Segment Tree) 희소 테이블(Sparse Table) 머지 소트 트리(Merge Sort Tree) 제곱근 분할법(Sqrt Decomposition) 헤비-라이트 분할(Heavy-Light Decomposition) 센트로이드 분할(Centroid Decomposition) 기타 여러 트리 형태의 자료 .. 이전 1 2 다음
