169. Square Root Decomposition

적당한 분할을 통해서 시간복잡도를 최적화하는 또 다른 방법을 알아본다.

 

제곱근 분할법(평방 분할, Square Root Decomposition)은 큰 구간을 구간 크기의 제곱근을 기준으로 분할한 다음 연산을 빠르게 처리하는 방법이다. 여기서 큰 구간은 크게 두 가지 형태로 나타나는데, 한 가지는 수열이고 다른 한 가지는 수 자체이다. 구간의 형태에 따라 제곱근 분할법을 적용하는 방식도 다르게 나타난다. 길이가 $n$인 수열에 제곱근 분할법을 적용할 때는 보통 이것을 $\sqrt{n}$ 정도의 길이를 갖는 구간 $\sqrt{n}$개로 분할한 다음 원하는 연산을 처리하는 방식이 주로 사용되지만, 수 자체에 제곱근 분할법을 적용할 때는 수를 $\sqrt{n}$ 이하와 $\sqrt{n}$ 이상의 두 그룹으로 나눈 다음 각각을 따로 처리하는 방식이 주로 사용된다. 일반적으로 제곱근 분할법을 다룰 때 구간이 수열인 경우만을 다루는 경우가 많지만, 구간이 수 자체인 경우의 처리 방법도 익숙해지는 것이 좋다. 구간이 수열인 경우는 모스 알고리즘이라는 이름으로 따로 다루고, 여기서는 구간이 수 자체인 경우를 살펴보기로 한다.

 

가장 간단한 예시로 약수의 개수를 구하는 문제를 살펴보자.

양의 정수 $n$이 주어질 때, $n$의 약수의 개수를 구하시오. $(1 \le n \le 10^{12})$

$n$의 제한이 $10^{12}$까지이므로 $1$부터 $n$까지 일일히 확인하는 방법은 너무 느리다. 이때 $1$부터 $\sqrt{n}$까지만 확인하는 방법은 꽤 많이 알려져 있다. 즉 이런 식으로 하는 것이다.

typedef long long LL;

int s = 0;
for(LL i = 1; i * i <= n; i++)
{
    if(n % i == 0)s++; // i는 n의 약수
}
for(LL i = 1; i * i < n; i++)
{
    if(n % i == 0)s++; // n/i는 n의 약수
}

이걸 더 간단하게 하면

typedef long long LL;

int s = 0;
for(LL i = 1; i * i <= n; i++)
{
    if(n % i == 0)s++; // i와 n/i는 n의 약수
    if(i * i == n)s--; // i == n/i인 경우 처리
}

이런 식으로 된다. 이번에는 아래의 그래프를 보자.

$xy = 60$의 그래프 개형이다. 이 그래프는 제$1$사분면에서 $x$좌표와 $y$좌표가 모두 정수인 점 $12$개를 지나는데, 이때의 $x$좌표와 $y$좌표는 모두 $60$의 약수이고, 지나는 점의 개수인 $12$가 $60$의 약수의 개수가 된다. 여기서 선형 시간에 $60$의 약수의 개수를 구한다면 탐색 범위는 초록색 선으로 표시한 것과 같다. 물론 약수를 구한다고 $0$을 탐색하는 일은 없겠지만 이해를 돕기 위한 부분이므로 적당히 이해하고 넘어가는 것을 권장한다.

제곱근까지만 확인하는 방법의 탐색 범위를 나타내 보면 훨씬 짧아지는 것을 알 수 있다.

즉 탐색 방향을 $x$축과 $y$축 두 방향으로 확장하는 것이다. 이때 탐색의 범위를 최소화하려면 위와 같이 두 방향의 탐색 범위가 최대한 비슷해지게 하면 된다. 비슷한 예제를 하나 더 살펴보자.

양의 정수 $n$이 주어질 때, $1$ 이상 $n$ 이하의 정수 $i$에 대해 $\lfloor \frac{n}{i} \rfloor$의 합을 구하시오. $(1 \le n \le 10^{12})$

이건 $1$사분면에 속하며 $x$좌표와 $y$좌표가 모두 정수인 점들 중 $x$축, $y$축, $y = \frac{n}{x}$의 그래프 사이에 둘러싸인 점의 개수를 구하는 것과 같다.

이것도 역시 $x$축과 $y$축 방향으로 탐색을 진행한다면 아래와 같이 세 부분으로 나눠서 각 영역에 속하는 점의 개수를 구한 다음 더하면 된다. 경계선에 있는 점들의 처리에 주의하자.

이밖에 다른 경우들을 연습문제들을 통해 알아보자. 위에 나온 예시는 그래프가 대칭이었는데 연습문제에서는 대칭과는 상관이 없는 상황들이 나타난다. 때때로 상당한 식 정리가 필요할 수도 있다.

 

[연습문제]

 

BOJ 1215. 잘못 작성한 요세푸스 코드 (Platinum IV)

$1$ 이상 $n$ 이하의 정수 $i$에 대해 $k \,\bmod\, i$의 합을 구해야 한다. 여기서 $\sqrt{k}$를 기준으로 생각하면 $i \le \sqrt{k}$인 경우는 그냥 다 해 보면 되고, $\sqrt{k} \le i \le k$인 경우 몫으로 가능한 값의 종류가 최대 $\sqrt{k}$개가 된다. 어떤 수를 연속된 정수들로 나누었을 때 몫이 같다면 나머지는 등차수열의 형태로 나타나므로 최대 $\sqrt{k}$개의 등차수열의 합을 다 더하면 이 구간을 처리할 수 있다. 그리고 $i > k$인 경우는 나머지가 항상 $k$이므로 쉽다.

 

BOJ 25952. Rectangles (Diamond V)

$O(n^2)$ 풀이를 많이 최적화하면 제한시간 안에 통과할 법도 하지만 깔끔하게 제곱근 분할법으로 풀어 보자. 점들을 $x$좌표가 같은 것끼리 묶으면 $\sqrt{n}$개 이상의 점이 속한 그룹은 최대 $\sqrt{n}$개만 존재한다. 그 그룹들은 직사각형의 꼭짓점을 $0$개, $2$개, 또는 $4$개 포함할 수 있는데, 네 점이 모두 $\sqrt{n}$개 이상의 점이 속한 그룹에 포함되는 경우는 투 포인터 등으로 $O(n \sqrt{n})$ 시간에 구할 수 있고 한 점도 포함되지 않는 경우는 std::map 같은 것을 쓰면 역시 $O(n \sqrt{n})$ 시간에 구할 수 있다. 마지막으로 두 점이 포함되는 경우는 포함되는 두 점을 기준으로 $\sqrt{n}$개 미만의 점이 속하는 그룹을 하나씩 확인하는 방식으로 $O(n \sqrt{n})$ 시간에 구할 수 있다. 그렇다면 $O(n \sqrt{n})$ 시간에 전체 문제를 해결할 수 있다.

 

CF 1780E. Josuke and Complete Graph (2400)

먼저 차이가 $k$인 $k$의 배수 두 개가 구간 $[l, r]$에 존재하면 가중치가 $k$인 간선이 존재한다는 것을 관찰해야 한다. 따라서 $r \ge 3l$인 경우는 답이 $\lfloor \frac{r}{2} \rfloor$가 된다. 만약 $r < 3l$인 경우 $\sqrt{l}$을 기준으로 분리해서 약간의 식정리를 통해 답을 구하면 된다. 레이팅은 *2400이지만 대회가 진행 도중 언레가 돼서 중간에 나간 참가자들이 많기 때문에 실제 난이도는 일반적인 *2400 문제들보다 쉬울 것이다.

 

→ solved.ac tag: sqrt_decomposition