Algorithm (134) 썸네일형 리스트형 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) 기타 여러 트리 형태의 자료 .. 152. Stable Marriage Problem 안정적인 결혼 문제(Stable Marriage Problem, SMP)는 크기가 동일한 두 집합에서 안정적인 매칭(Stable Matching)을 찾는 문제이다. 두 집합 간의 안정적인 매칭이라는 것은 다음과 같다. 각 집합의 원소는 상대 집합의 원소들에 대한 서로 다른 선호도를 가진다. 첫 번째 집합과 두 번째 집합의 원소가 일대일로 매칭되어 있다. 첫 번째 집합에 속한 원소 $A$, $B$가 두 번째 집합에 속한 원소 $C$, $D$와 각각 매칭되어 있을 때 $A$가 $C$보다 $D$를 선호하면서 $D$가 $B$보다 $A$를 선호하는 경우는 존재하지 않는다. 세 번째 조건을 다시 설명하면 서로 매칭되지 않은 두 원소 모두가 상대 원소를 자신과 매칭된 원소보다 더 선호하는 경우가 존재하지 않는다는 것.. 141. Bipartite Matching 플로우 문제를 풀다 보면 특수한 형태의 그래프가 자주 등장하는 것을 알 수 있다. 아래의 그래프를 보자. 소스에서 첫 번째 그룹의 정점들로 가는 간선들이 있고, 첫 번째 그룹의 정점들에서 두 번째 그룹의 정점들로 가는 간선이 있고, 두 번째 그룹의 정점들에서 싱크로 가는 간선이 있다. 각 간선의 용량은 전부 $1$이다. 위 그래프에서 소스와 싱크를 없애고 간선의 방향 표시도 없애면 아래와 같은 이분 그래프가 된다. 간선의 용량이 전부 $1$이므로, 이 그래프에서 최대 유량을 구하는 문제는 첫 번째 그룹에 속하는 정점들과 두 번째 그룹에 속하는 정점들 간의 최대 매칭(Maximum Matching)의 크기를 찾는 문제로 생각할 수 있다. 앞서 소스와 싱크에 연결된 간선들의 용량도 전부 $1$이었으므로 각각.. 140. Edmonds-Karp Algorithm 다음과 같은 그래프에서 포드-풀커슨 알고리즘으로 최대 유량을 구하는 경우를 생각해 보자. 포드-풀커슨 알고리즘은 증가 경로를 정하는 방법을 정의하지 않으므로, 운이 좋으면 증가 경로 $\text{S}$ - $\text{A}$ - $\text{T}$로 $10000$의 유량을 보내고 증가 경로 $\text{S}$ - $\text{B}$ - $\text{T}$로 $10000$의 유량을 보내서 두 번의 탐색으로 $20000$의 유량을 보낼 수 있다. 하지만 이 그래프에는 $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{T}$라는 증가 경로가 존재한다. 만약 이 경로를 선택할 경우 보낼 수 있는 유량은 $1$이고, 그러면 간선들의 유량은 다음과 같이 변한다. 이제 $\text{S.. 이전 1 2 3 4 5 ··· 17 다음
