- 알고리즘
- 제곱근 분할법
제곱근 분할법 (Square Root Decomposition)
문제
크기가 $N$인 정수 배열 $A$가 있고, 여기서 다음과 같은 연산을 최대 $M$번 수행해야 하는 문제가 있습니다.
- 구간 $l$, $r$ ($l ≤ r$)이 주어졌을 때, $\min(A[l], A[l+1], \dots , A[r])$을 구해서 출력하기
- $i$번째 수를 $v$로 바꾸기 ($A[i] = v$)
1번 연산 $\min(A[l], A[l+1], \dots , A[r])$을 구하기 위해 소스 1과 같이 모두 더하는 방법이 있습니다.
소스 1
소스 1의 시간 복잡도는 $O(N)$입니다. 2번 연산 $A[i] = v$는 $O(1)$ 입니다. 연산을 최대 $M$번 수행해야 하니 연산 하나의 시간 복잡도는 $O(N)$이 됩니다. 총 시간 복잡도는 $O(NM)$입니다.
제곱근 분할법
제곱근 분할법을 사용하려면 크기가 $N$인 배열을 크기가 $\sqrt{ N }$인 그룹으로 나누고, 각 그룹의 최솟값을 별도로 저장해야 합니다.
그룹의 크기가 $\sqrt{ N }$이니, 그룹의 개수도 $\sqrt{ N }$개입니다. $N$이 제곱수가 아닌 경우에는 그룹의 크기로 $\lfloor \sqrt{ N } \rfloor$를 사용합니다.
그룹의 크기는 $r$, 그룹의 개수는 $g$, $i$번째 그룹에 들어있는 수의 최솟값은 $D[i]$로 표현합니다.
예시
$N$ = ($1 \le N \le 20$)
- 그룹의 크기 = $r$ = $\lfloor \sqrt { N } \rfloor$ =
- 그룹의 개수 = $g$ = $\lceil N / r \rceil$ =
$i$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
---|---|---|---|---|---|---|---|---|---|---|---|
$A[i]$ | $2$ | $3$ | $2$ | $4$ | $3$ | $8$ | $4$ | $9$ | $7$ | $5$ | $3$ |
그룹 | $0$ | $1$ | $2$ | $3$ | |||||||
$D[i]$ | $2$ | $3$ | $4$ | $3$ |
소스 2를 이용해 $D$를 구할 수 있습니다.
소스 2
변경
2번 연산은 $i$번째 수를 $v$로 바꾸는 연산입니다.
이 경우 $i$번째 수가 포함된 그룹의 $D$만 변경하면 됩니다. 그룹에 포함된 수의 최솟값을 구하려면, 그 그룹에 포함된 모든 수를 조사하면 됩니다. 그룹에 포함된 수의 개수는 $r = \lfloor \sqrt{ N } \rfloor$이니 시간 복잡도는 $O(\sqrt { N })$입니다.
소스 3과 같이 구현할 수 있습니다.
소스 3
update(a, d, r, index, v)
는 a[index]
에 저장되어 있는 값을 변경하고, index
가 해당하는 그룹의 최솟값도 변경하는 함수입니다.
변경을 구현하기 위해 먼저, a[index]
에 저장되어 있는 값을 변경합니다.
그 다음, index
가 속한 그룹의 번호를 구해 이를 group
에 저장하고, 해당 그룹의 첫 번째 인덱스 start
와 마지막 인덱스 + 1인 end
를 구합니다.
마지막으로 그룹에 들어있는 수 전체를 순회하면서 그룹의 최솟값 d[group]
을 구합니다.
최솟값 구하기
$\min(A[l], A[l+1], \dots , A[r])$을 구하기 방법에 대해서 알아봅시다.
다음과 같은 두 가지 경우로 나눌 수 있습니다.
- $l$과 $r$이 같은 그룹에 속한 경우
- $l$과 $r$이 같은 그룹에 속하지 않은 경우
같은 그룹에 속한 경우에는 그룹의 최솟값을 저장한 배열 $D$를 이용할 수 없습니다. 최솟값이 구간 $[l,r]$에 속하지 않을 수도 있기 때문입니다. 따라서, 소스 1과 같이 $l$부터 $r$까지를 순회해서 최소값을 구해야 합니다. 하나의 그룹에 포함된 수의 개수는 $r = \lfloor \sqrt{ N } \rfloor$이기 때문에, 이 경우 시간 복잡도는 $O(\sqrt { N })$입니다.
다른 그룹에 속한 경우는 그룹을 다음과 같이 세 가지 경우로 다시 나눌 수 있습니다.
- $l$이 속한 그룹
- $r$이 속한 그룹
- 위의 두 그룹 사이에 있는 그룹
$l$이 속한 그룹과 $r$이 속한 그룹에서는 $D$를 이용할 수 없기 때문에, $l$부터 $l$이 속한 그룹의 끝까지, $r$이 속한 그룹의 시작부터 $r$까지 순회해서 최솟값을 구해야 합니다. 각각의 경우 모두 최대 $\sqrt{ N }$번의 비교를 해야하니 시간 복잡도는 $O(\sqrt { N })$입니다.
두 그룹 사이에 있는 그룹의 경우에는 그 그룹에 속한 모든 수가 구간 $[l,r]$에 포함되기 때문에, $D$를 이용할 수 있습니다. 그룹의 개수도 $\sqrt{ N }$개이니, 시간 복잡도는 $O(\sqrt{ N })$입니다.
시간 복잡도를 정리해보면 다음과 같습니다.
- $l$과 $r$이 같은 그룹에 속한 경우 = $O(\sqrt{ N })$
- $l$과 $r$이 같은 그룹에 속하지 않은 경우 = $O(3 \times \sqrt{ N })$ = $O(\sqrt{ N })$
변경도 $O(\sqrt{ N })$에 구할 수 있습니다.
소스 4와 같이 구현할 수 있습니다.
최솟값 구하기 예시
- $A = $ 로
- $1 \le N \le 20$
- $1 \le A[i] \le 99$
$i$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
---|---|---|---|---|---|---|---|---|---|---|---|
$A[i]$ | $2$ | $3$ | $2$ | $4$ | $3$ | $8$ | $4$ | $9$ | $7$ | $5$ | $3$ |
그룹 | $0$ | $1$ | $2$ | $3$ | |||||||
$D[i]$ | $2$ | $3$ | $4$ | $3$ |
- 최솟값 구하기: $l$ = , $r$ =
소스 4
start
는 구간의 시작 $l$, end
는 구간의 끝 $r$을 의미합니다.
start/r == end/r
인 경우는 같은 그룹에 속한 경우입니다. 소스 1과 같은 방식으로 구현한 것을 확인할 수 있습니다.
같은 그룹에 속하지 않은 경우는 3개의 작은 부분으로 나누어져있습니다. 첫 while
은 start
가 속한 그룹에서 최솟값을 구하는 부분, 그 다음 while
는 end
가 속한 그룹에서 최솟값을 구하는 부분입니다.
이제 남은 것은 두 그룹 사이에 속하는 그룹의 최솟값과 비교하는 부분이고, 이 부분은 마지막 for
입니다.
14438 - 수열과 쿼리 17
이 글의 가장 처음에 설명한 문제와 같은 문제입니다. 소스 5로 해결할 수 있습니다.
소스 5
2042 - 구간 합 구하기
최솟값 대신 합을 구하는 문제입니다. 소스 6으로 해결할 수 있습니다.
소스 6
최솟값과 다르게 합은 뺄셈을 이용할 수 있기 때문에 update
의 구현이 간단해집니다.
세그먼트 트리
제곱근 분할법을 사용해서 해결할 수 있는 문제의 일부는 세그먼트 트리로 해결할 수 있습니다. 세그먼트 트리의 변경, 쿼리의 시간 복잡도는 $O(\lg{ N })$으로 제곱근 분할법보다 훨씬 빠릅니다. 세그먼트 트리를 사용하는 것이 훨씬 좋습니다.
모스 알고리즘 (Mo's Algorithm)
제곱근 분할법은 모스 알고리즘의 기본 아이디어가 되는 알고리즘입니다. 모스 알고리즘을 구현할 때 이외에는 구현할 일이 많지 않습니다.