제곱근 휴리스틱 - 알고리즘카

제곱근 휴리스틱은 $n$개의 원소로 이루어진 어떤 집합을 $\sqrt{n}$개씩의 원소로 이루어진 블록으로 나누면 그 블록 자체의 개수는 $\sqrt{n}$개를 넘지 않는다는 사실에 기반한 여러 가지 방법과 자료 구조를 통틀어 이르는 이름입니다.

이 글의 핵심 등식은 $\sqrt x = \frac{x}{\sqrt x}$입니다.

#무거운 객체와 가벼운 객체로 나누기

누구나 아는 루트 시간 소인수분해 알고리즘은 수 $n$의 모든 「큰」 약수 $d \geq \sqrt n$에 어떤 「작은」 약수 $\frac{n}{d} \leq n$이 대응한다는 사실에 기반합니다.

이와 비슷한 유용한 성질(작은 객체는 작고, 큰 객체는 많지 않다는 성질)은 다른 객체에서도 찾아볼 수 있습니다.

#긴 문자열과 짧은 문자열

문제. 문자열 집합에 대한 세 가지 유형의 연산을 온라인으로 처리해야 합니다:

집합에 문자열을 추가합니다.
집합에서 문자열을 삭제합니다.
주어진 문자열이 집합의 모든 문자열에 부분 문자열로 몇 번 등장하는지 구합니다.

한 가지 해법은 다음과 같습니다. 모든 문자열을 짧은 문자열($|s| < \sqrt l$)과 긴 문자열($|s| \geq \sqrt l$)로 나눕니다. 여기서 $l$은 모든 문자열의 길이의 합을 의미합니다. 긴 문자열은 많지 않으며 최대 $\sqrt l$개라는 점에 주목하십시오.

쿼리는 다음과 같이 처리하겠습니다:

해시 테이블을 하나 만들어 두고, 추가 또는 삭제 쿼리를 처리할 때마다 해당 문자열의 모든 짧은 부분 문자열의 해시에 대해 각각 1을 더하거나 뺍니다. 이는 전체적으로 $O(l \sqrt l)$에 할 수 있습니다: 각 문자열마다 $O(\sqrt l)$개의 서로 다른 길이를 순회하며 윈도우로 문자열 전체를 훑으면 됩니다.
세 번째 유형의 쿼리가 짧은 문자열에 대한 것이라면, 단순히 그 문자열의 해시를 계산하고 해시 테이블에 저장된 값을 확인하면 됩니다.
긴 문자열에 대한 세 번째 유형의 쿼리에서는 삭제되지 않은 모든 문자열을 살펴보아도 됩니다. 이러한 경우는 많지 않기 때문입니다. 따라서 새 문자열의 모든 등장 위치를 선형 시간에 찾을 수 있다면, 이 역시 $O(l \sqrt l)$에 동작합니다. 예를 들어, s#t 형태의 모든 문자열에 대해 Z 함수를 계산할 수 있습니다. 여기서 $s$는 쿼리로 주어진 문자열이고 $t$는 집합에 있는 문자열입니다. 다만 여기에는 주의할 점이 있습니다. $s$는 클 수 있고 작은 문자열 $t$는 많을 수 있으므로, 먼저 $s$에 대해서만 Z 함수를 계산한 다음 각 $t$를 가상으로 그 뒤에 덧붙여 가며 함수를 이어서 계산해야 합니다.

때로는 무거운 객체와 가벼운 객체를 따로 다루는 접근이 필요하지 않지만, 이 아이디어 자체는 몇몇 단순한 풀이가 생각보다 빠르게 동작한다는 것을 알아차리는 데 도움이 됩니다.

#그래프의 삼각형

문제. 정점 $n$개와 간선 $m \approx n$개로 이루어진 그래프가 주어집니다. 이 그래프에서 길이가 3인 사이클의 개수를 구해야 합니다.

어떤 정점이 $\sqrt n$개보다 많은 다른 정점과 연결되어 있으면 그 정점을 무거운 정점이라 부르고, 그렇지 않으면 가벼운 정점이라 부르겠습니다.

가능한 4가지 경우를 모두 살펴보면서, 서로 연결된 정점 세 개 묶음의 개수를 추정해 봅시다.

사이클에 무거운 정점이 없는 경우입니다. 사이클의 임의의 간선 $(a, b)$를 생각해 봅시다. 세 번째 정점 $c$는 인접 리스트 $g_a$와 $g_b$의 합집합에 속해야 하는데, 두 정점이 모두 가벼우므로 그러한 정점은 많아야 $\sqrt n$개입니다. 따라서 이 유형의 사이클은 모두 합해 많아야 $O(m \sqrt n)$개입니다.
사이클에 무거운 정점이 하나 있습니다. 마찬가지로 ‘가벼운’ 간선이 하나 있으므로, 이러한 사이클 역시 $O(m \sqrt n)$개입니다.
사이클에 무거운 정점이 두 개 있는 경우입니다. 이를 $a$와 $b$로, 가벼운 정점을 $c$로 표기합시다. 쌍 $(a, c)$를 고정합시다. 간선이 모두 그만큼 있으므로 이렇게 하는 방법은 $O(m)$가지입니다. 무거운 정점이 모두 그만큼 있으므로, 이 간선에 대해 간선 $(a, b)$는 $O(\sqrt n)$개를 넘지 않습니다. 결국 이러한 사이클은 모두 합쳐 $O(m \sqrt n)$개를 넘을 수 없습니다.
모든 정점이 무거운 정점입니다. 마찬가지로, 앞의 경우를 분석할 때 세 번째 정점의 종류는 어디에서도 사용되지 않았습니다. 중요한 것은 무거운 정점 $b$가 많지 않다는 점뿐입니다.

결과적으로 그래프에서 길이가 3인 사이클은 그리 많지 않을 수 있으며, 많아야 $O(m \sqrt n)$개입니다.

해법 자체는 매우 간단합니다. 그래프의 정점을 차수에 따라 정렬한 뒤, $v \rightarrow u \rightarrow w, v \le u \le w$ 형태의 모든 경로를 순회하면서 간선 $v \rightarrow w$가 존재하는지 확인합니다.

vector<int> g[maxn], p(n); // исходный граф и список номеров вершин
iota(p.begin(), p.end(), 0); // 0, 1, 2, 3, ...

// чтобы не копипастить сравнение:
auto cmp = [&](int a, int b) {
    return g[a].size() < g[b].size() || (g[a].size() == g[b].size() && a < b);
};

// в таком порядке мы будем перебирать вершины
sort(p.begin(), p.end(), cmp);

// теперь отсортируем списки смежности каждой вершины
for (int v = 0; v < n; ++v)
    sort(g[v].begin(), g[v].end(), cmp);

// рядом с каждой вершиной будем хранить количество
// ранее просмотренных входящих рёбер (v -> w)
vector<int> cnt(n, 0);
int ans = 0;

for (int v : p) {
    for (int w : g[v])
        cnt[w]++;
    for (int u : g[v]) {
        if (cmp(v, u))
            break;
        for (int w : g[u]) {
            if (cmp(u, w))
                break; // если ребро плохое -- не берем треугольник
            ans += cnt[w]; // если в графе нет петель, то cnt[w] = {0, 1}
        }
    }
    // при переходе к следующему v массив нужно занулить обратно
    for (int w : g[v])
        cnt[w]--;
}

#$O(S \sqrt S)$ 배낭 문제

무게가 $w_1$, $w_2$, $\ldots$, $w_n$이고 $\sum w_i = S$를 만족하는 물건 $n$개가 있다면, 표준적인 DP로 배낭 문제를 $O(S \cdot n)$ 시간에 풀 수 있습니다. 문제를 더 빠르게 풀기 위해, 물건의 개수가 $O(\sqrt S)$가 되도록 만들어 봅시다.

서로 다른 무게의 개수는 $O(\sqrt S)$개가 된다는 점에 주목합시다. 왜냐하면 합이 $S$인 서로 다른 임의의 $k$개의 수에 대해

$$ S = w_1 + w_2 + \ldots + w_n \geq 1 + 2 + \ldots + k = \frac{k \cdot (k+1)}{2} $$

따라서 $k \leq 2\sqrt S = O(\sqrt S)$임을 알 수 있습니다.

이제 가중치 집합에 $k$번 나타나는 어떤 가중치 $x$를 생각해 봅시다. $k$를 2의 거듭제곱으로 «분해»하여, 이 가중치의 $k$개 항목 전부 대신 가중치 $x$, $2 \cdot x$, $4 \cdot x$, $\ldots$, $(k - 1 - 2^t) \cdot x$를 추가합니다. 여기서 $t$는 $2^t − 1 \leq k$를 만족하는 최대 정수입니다. $q \cdot x$ ($q \leq k$) 꼴의 합 전부를, 그리고 오직 그것들만을 여전히 만들 수 있음을 쉽게 알 수 있습니다.

사실 알고리즘은 이것이 전부입니다: 모든 고유한 무게 값에 대해 이 연산을 수행한 다음, 표준 풀이를 실행합시다. 각 무게마다 최대 $\log S$개의 무게만 남겼고 서로 다른 무게는 모두 $O(\sqrt S)$개였으므로, 새로운 물건의 개수가 $O(\sqrt S \log S)$이 된다는 것을 이미 쉽게 알 수 있습니다.

연습 문제. 실제로는 물건의 개수가 $O(\sqrt S)$개임을 증명하십시오.

참고. 고전적인 배낭 문제 풀이는 bitset을 사용하면 몇 자릿수만큼 빠르게 만들 수 있습니다.

또한 제곱근 휴리스틱은 자료 구조와 쿼리 처리의 맥락에서도 사용할 수 있습니다.