Small to Large Trick

Intro

Small to Large Trick은 집합을 서로 합치는 연산을 최적화 할 때 사용하는 트릭입니다. (한국에서는 작은거 큰거 라고도 불리는 모양입니다.) 예를 들어 $n$개의 disjoint한, 크기가 1인 집합을 서로 합쳐야 한다고 합시다. 당연하게도 크기가 $a$인 집합에 크기가 $b$인 집합을 추가하는 데는 $O(b)$의 시간이 걸립니다. 이걸 Naive하게 구현한다면 얼마의 시간이 걸릴까요? 만약 두 집합을 합칠 때 아무 집합을 다른 집합에 합치는 것을 계속 반복한다면, 최악의 경우에는 크기가 가장 큰 집합을 크기가 가장 작은 집합에 계속해서 넣으면서 총 $O(N^2)$의 시간이 걸릴 것입니다. 하지만 어지간히 멍청한 알고리즘이 아니고서야, 크기가 큰 집합을 작은 집합에 합칠리가 없습니다. 자명하지만, 두 집합을 합쳐야 한다면 작은 집합을 큰 집합에 합치는 것이 더 빠르기 때문입니다. 그런데 이렇게 작은 집합을 큰 집합에 합치는 규칙만 지켜도 최종적으로는 모든 집합을 항상 $O(N \lg N)$에 합쳐진다는 것을 아는 것은 생각보다 자명하지 않아 보입니다. 이 글에서는 왜 이 알고리즘이 이렇게 빠르게 동작하는지를 알아보고, 이를 활용할 수 있는 문제들에 대해 다룹니다.

Proof

증명은 매우 간단합니다. 크기가 $p$인 집합 $A$와 $q$인 집합 $B$가 있다고 하고, $p \ge q$라고 합시다. $A$와 $B$가 합쳐질 때, 움직이는 것은 $B$의 원소들입니다. 여기서 주목할 점은 $B$의 원소들이 옮겨진 후 새로 존재하게 되는 집합의 크기는 $p+q \ge 2q$ 이상이라는 것입니다. 결국 옮겨지는 원소들은 항상 현재 자신의 집합의 크기보다 2배 이상 큰 집합에 존재하게 됩니다. 따라서 각 원소들은 한번 옮길 때마다 속한 집합의 크기가 2배 이상 증가하므로 $O(\lg N)$번을 넘어 집합 사이를 이동할 수 없습니다. 총 원소가 N개이므로, 모든 집합을 합쳐주었을 때 시간복잡도는 $O(N \lg N)$이 됩니다.

Step-Up

사실 트릭이라고 부르기도 민망한 이 기법을 적용하는 것은 주로 트리에서입니다. 트리에서 집합을 관리해야 하는 경우는 일반적으로 어떤 노드와 그 노드의 서브트리에 관한 쿼리를 처리해야 하는 경우인데, 만약 상위 노드가 하위 노드에 대한 의존성을 가지고 있는 경우라면 하위 노드에 대한 처리를 모두 완료하고 집합을 위쪽으로 합쳐줌으로서 빠르게 트리에서의 문제를 해결할 수 있습니다. 말로 들으면 이해하기 힘들 수도 있으니 문제를 보면서 확인해봅시다.

트리의 색과 쿼리

선린인터넷고 동아리 대회 Unicon에서 나온 문제라서 출제된 지 오래되지는 않았지만, Small to Large Trick을 설명할 때 항상 등장하는 문제 중 하나입니다. (BOJ 17469번) 이 문제에 쉽게 접근하기 위해서는 다음과 같은 선수 지식이 필요할 수 있습니다: 연결된 트리를 모두 단일 정점으로 쪼갤 때 오프라인으로 쿼리를 처리하는 법. 다음과 같은 문제에서 도움을 얻을 수 있습니다 : 2016 KOI 중등부 3번 트리, BOJ에선 13306번입니다. 먼저 이 문제를 해결하고 밑의 내용을 보는 것을 강력히 추천합니다.

문제 요약

각 정점에 색깔이 매겨져 있는 트리가 있을 때, 다음과 같은 두 가지 쿼리를 처리해야 합니다. 모든 쿼리를 처리한 이후에는 트리에서 간선이 없어짐이 보장됩니다.

• 간선 하나를 삭제한다.
• 정점 $v$에서 갈 수 있는 모든 정점의 색깔의 종류를 구한다.

문제 풀이

문제에 다음과 같이 접근해 봅시다. 어차피 쿼리가 끝나고 나서는 모든 간선이 제거된 상태일테니, 간선을 제거하는 쿼리보다는 상황을 완전히 거꾸로 뒤집어 모든 노드가 독립적인 상황에서 간선을 추가하는 상황으로 바꿉시다. 이렇게 한다면 문제를 크게 직관적으로 바꾸어줄 수 있습니다. 이제 문제는 포레스트가 있을 때, 포레스트 내의 두 트리를 합치는 연산과 특정 트리의 색깔의 종류를 출력하는 문제로 바뀌었습니다.

단순히 위에서 언급했던 대로 집합을 합쳐 주면 중복된 색깔을 처리하기가 상당히 벅찹니다. 어떻게 하면 두 집합을 합칠 때 중복된 색깔을 제거해줄 수 있을까요? 집합을 합쳐줄 때 vector 등을 사용하는 대신 중복된 원소를 허용하지 않는 이진 탐색 트리, 대표적으로 set을 사용해주면 됩니다. 물론 그만큼 시간복잡도가 증가하기는 하지만, 각 원소가 추가되거나 제거되는데는 $O(\lg n)$ 시간이 걸리므로 크게 영향을 주지는 않습니다. 간선 추가(사실은 제거) 쿼리가 들어올 때마다 두 트리 중 색깔 종류의 집합 크기가 작은 것을 큰 것에 합쳐주면서 각 트리가 가지고 있는 색깔의 종류를 관리해 주면 총 $O(n \lg ^2 n)$ 시간에 해결할 수 있습니다.

소스 코드

#include <bits/stdc++.h>

using namespace std;
typedef tuple<int, int, int> tp;
typedef pair<int, int> pii;

int n,q;
int par[100005], ptr[100005];
vector<pii> query;
vector<int> ans;

set<int> S[100005];

int fi(int x) {
    if (x == ptr[x]) return x;
    else return ptr[x] = fi(ptr[x]);
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 2; i <= n; i++)
        scanf("%d", &par[i]);
    for (int i = 1; i <= n; i++) {
        int cl;
        scanf("%d", &cl);
        S[i].insert(cl);
        ptr[i] = i;
    }
    int l = 0, sz=0;
    for (int i = 0; i < n + q - 1; i++) {
        int t1, t2;
        scanf("%d %d", &t1, &t2);
        query.emplace_back(t1, t2);
    }
    reverse(query.begin(), query.end());
    for (pii x : query) {
        int tp = x.first, k = x.second;
        if (tp == 1) {
            int p = par[k];
            p = fi(p), k = fi(k);
            if (S[k].size() >= S[p].size()) swap(p, k);
            ptr[k] = p;
            for (auto it = S[k].begin(); it != S[k].end(); it++)
                S[p].insert(*it);
            S[k].clear();
        }
        else
            ans.push_back(S[fi(k)].size());
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans) printf("%d\n", x);
    return 0;
}

닌자 배치

APIO 2012 1번 문제입니다. (BOJ 4002번) 예전에는 APIO에서 이렇게 쉬운 문제도 나왔다는 것을 염두에 두면서, 문제를 해결해 봅시다.

문제 요약

• 트리와 예산이 주어지고, 각 정점은 비용과 레벨을 가집니다.
• 어떤 정점을 고르면 그 정점의 점수는 그 정점의 레벨에, 그 정점의 서브트리에서 적절하게 고를 수 있는 정점의 수를 곱한 것이 됩니다. 정점을 적절하게 고른다는 것은, 고른 정점의 비용 합이 예산을 초과하지 않는 것을 말합니다.
• 정점을 하나 골랐을 때 얻을 수 있는 최대 점수를 출력합니다.

문제 풀이

그리디한 접근으로, 어떤 정점 $v$를 선택했을 때 $v$의 서브트리에서 고를 수 있는 최대 정점의 수는 서브트리에서 비용이 낮은 순서대로 골라 정점을 선택했을 때의 정점의 수와 같습니다. (너무 자명합니다!) 따라서 만약 각 정점마다 정점의 서브트리 내에서 예산을 초과하지 않도록 정점을 비용이 낮은 것부터 최대로 고를 수 있는 수가 몇인지를 빠르게 찾아준다면, 그 뒤는 $O(N)$으로 레벨과 곱한 최댓값을 계산해줄 수 있을 것입니다.

따라서 결국 문제가 되는 것은 정점을 비용이 낮은 것 부터 관찰했을 때 몇 개의 정점을 예산을 초과하지 않고 고를 수 있는지가 됩니다. 이는 위에 언급한 Small to Large Trick으로 간단하게 해결할 수 있습니다. 각 정점의 비용을 합쳐야 할 unit 단위의 집합이라고 보고, 이를 부모 쪽으로 합쳐 가면서 각 정점을 보고 있을 때는 그 정점의 서브트리에 존재하는 모든 비용을 집합에 들고 있으면 됩니다. 이러면 집합에서 $x$개의 원소를 작은 것 부터 선택했을 때 예산을 초과하지 않게 하는 최대의 $x$를 빠르게 구하는 것만 해 주면 됩니다. 여기서 이진 탐색 트리를 잘 쓰면 Naive하게도 $O(n \lg ^3 n)$에 하거나 $O(n \lg^2 n)$까지도 줄일 수 있겠지만, 느리거나 구현이 복잡합니다. 하나 할 수 있고, 당연히 해야 하는 관찰은 집합이 합쳐지며 올라갈수록 사용할 수 있는 원소가 늘어남에 따라 아래쪽에서 사용되지 않은 원소는 위쪽에서도 영원히 사용될 일이 없다는 것입니다. 따라서 집합을 관리해 줄 때 합치고 나서 가장 큰 원소부터 제거하면서 집합에 남은 원소가 예산을 만족하는지 확인해 줄 수 있고, 이때 집합의 크기가 뽑을 수 있는 원소의 최대 개수임을 알 수 있습니다. 원소의 추가와 가장 큰 원소의 제거 쿼리만이 있으므로, priority queue를 사용할 수 있고 총 시간복잡도는 $O(n \lg ^2 n)$이 됩니다.

소스 코드

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;
typedef long long ll;

int n, root; ll m, ma;
vector<int> child[101010];
int par[101010]; ll leader[101010], cost[101010];
int idx[101010];
priority_queue<ll> pq[101010];

ll solve(int v) {
    ll val = cost[v];
    for (int th : child[v]) {
        val += solve(th);
        int a = idx[v], b = idx[th];
        if (sz(pq[a]) > sz(pq[b])) swap(a, b);
        while (!pq[a].empty()) {
            pq[b].push(pq[a].top());
            pq[a].pop();
        }
        while (val > m) {
            val -= pq[b].top();
            pq[b].pop();
        }
        idx[v] = b;
    }
    ma = max(ma, leader[v] * sz(pq[idx[v]]));
    return val;
}

int main() {
    fio();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> par[i] >> cost[i] >> leader[i];
        if (!par[i]) root = i;
        child[par[i]].push_back(i);
        pq[i].push(cost[i]);
        idx[i] = i;
    }
    solve(root);
    cout << ma;
    return 0;
}

Extension

이와 같은 관찰은 여러 곳에서 유용하게 쓰입니다. Union-Find Tree에서 시간복잡도를 줄이기 위해서도 Small to Large Trick이 사용됩니다. 흔히 Union-Find Tree에서 Path Compression만 사용하는 것이 더 빠르기에 Rank Optimization이 천대받는 경향이 있으나, 롤백이 필요한 경우, 특히 Offline Dynamic Connectivity Problem 같은 경우에는 Path Compression을 사용하지 못하므로 Rank Optimization만을 사용해야 합니다. 이때 Rank Optimization은 트리의 구조를 크게 훼손시키지 않으면서 간단하게 Union-Find의 시간복잡도를 $O(\lg n)$으로 유지시켜줍니다. 참으로 혜자라고 할 수 있겠습니다. (사실 흔히 사용하는 Rank Optimization은 이 글에서 설명하는 크기 기반 기법과는 약간 다르지만, 전체적인 맥락은 유사합니다.)

이 글에서는 집합을 이용해서 트리와 서브트리에 대한 쿼리를 처리하는 문제를 다뤘지만, 사실 이는 서브트리가 아니라 트리 위에서의 경로에도 적용될 수 있습니다. 이 아이디어를 확장한 자료구조가 Heavy Light Decomposition, 줄여서 HLD로, 트리 위의 경로를 적절히 쪼개서 트리 위 경로에 대한 쿼리를 일반적으로 $O(\lg^2 n)$에 처리할 수 있도록 만들어줍니다.

깊은 관련은 없지만 절반으로 쪼개서 트리를 관리하는 아이디어라면 Centroid Decomposition 또한 있습니다. 트리를 가능한 한 절반 이상으로 잘 쪼개는 정점을 계속해서 찾고 이를 바탕으로 분할 정복을 하는 알고리즘입니다. 국내에 좋은 자료가 많은 것 같지는 않지만, 관심 있으시면 한번 찾아보시는 것을 추천드립니다.

Problems which left as exercise

아직 제가 풀어보지 않은 문제가 섞여 있기 때문에, 부정확할 수 있습니다. 참고 부탁드립니다.

Facebook Hacker Cup 2018 Round 2 Jack's Candy Shop

BOJ 16858 고양이 소개팅

BOJ 8211 Tree Rotations

BOJ 16231 내가 그린 라이언 그림

BOJ 12736 Fireworks : Slope Trick 연습문제로 더 널리 알려져 있습니다.

다음 문제집을 많이 참고했습니다.