Algorithm/I. Data Structures & Advanced Algorithms (13) 썸네일형 리스트형 161. 2D Segment Tree & 2D Fenwick Tree $2$D 세그먼트 트리($2$D Segment Tree)는 세그먼트 트리를 $2$차원으로 구성한 것이다. 즉 $1$차원 세그먼트 트리들이 여러 개 존재하고 여기서 같은 위치에 있는 노드들로 구성된 세그먼트 트리들이 추가로 존재하는 방식이다. 다음과 같이 $4 \times 4$ 크기의 테이블이 존재할 때 $2$차원 세그먼트 트리를 어떻게 구성하는지 알아보자. A B C D E F G H I J K L M N O P $1$차원 세그먼트 트리를 구현할 때 $1$차원 배열을 선언했다. 비슷하게 $2$차원 세그먼트 트리를 $2$차원 배열로 구현할 것이다. 그러면 첫 번째 인덱스를 행, 두 번째 인덱스를 열에 대응해서 각 노드가 어느 범위의 데이터를 저장할지 결정할 수 있다. 더보기 첫 번째 인덱스로 다음과 같이 .. 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 다음
