195. Small to Large Technique

첫 번째로 알아볼 최적화 기법은 작은 집합에서 큰 집합으로 합치는 테크닉(Small to Large Technique)^[각주:1]으로, 분리 집합을 조금 더 발전시킨 것으로 이해할 수 있다. 즉, 기존의 분리 집합이 '원소 $x$가 속한 집합은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다면 이 스몰 투 라지 기법은 '집합 $S$에 속한 원소들은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다고 보면 된다. 물론 두 개를 같이 쓰면 양방향 질의 처리가 가능하다.

 

어떤 집합에 속한 원소들이 무엇인지를 알아야 하기 때문에 집합이 합쳐질 때마다 집합 내의 원소들도 하나로 합쳐야 하는데, 여기서 항상 원소의 수가 더 적은 집합을 원소의 수가 많은 집합에 합치면 어느 정도의 속도를 보장한다는 것이 작은 집합에서 큰 집합으로 합치는 테크닉의 원리이다. 그러면 속도가 어떻게 된다는 건지 시간복잡도를 계산해 보자.

 

$n$개의 집합이 있고, 처음에 각 집합에 원소가 하나씩 있다고 하자. 여기서 집합을 $(n - 1)$번 합쳐서 원소 $n$개를 포함하는 큰 집합으로 만드는 과정을 생각해 보기로 한다. 집합을 합칠 때 작은 집합의 원소들을 큰 집합으로 이동하므로, 어떤 원소가 집합이 합쳐지면서 다른 집합으로 이동했을 경우 그 원소가 속한 집합의 크기는 $2$배 이상으로 증가한다. 그런데 모든 집합이 하나로 합쳐졌을 때 그 집합의 크기는 $n$이므로, 각각의 원소는 최대 $\lg n$번만 다른 집합으로 이동할 수 있다. 원소의 수가 총 $n$이므로 집합을 전부 합치더라도 원소의 이동은 최대 $n \lg n$번만 일어난다는 것을 알 수 있다. 또한 집합의 크기를 비교하는 연산도 최대 $(n - 1)$번 해야 하기 때문에 집합의 크기를 구하는 연산의 시간복잡도도 필요한데, 이건 C++의 std::set 등 많은 집합 라이브러리를 사용하면 상수 시간에 작동하는 내장 함수가 있기 때문에 큰 문제가 되지는 않는다.

 

따라서 이걸 그대로 구현하면 전체 시간복잡도는 $O(n \lg n)$이 된다. 만약 집합이 초기에 원소를 여러 개 포함해서 전체 원소의 수가 $m$으로 증가한다고 해도 각각의 원소가 최대 $\lg m$번만 다른 집합으로 이동할 수 있다는 점은 그대로 적용되기 때문에 전체 시간복잡도가 $O(m \lg m)$임을 알 수 있다.

 

그러면 이 테크닉을 언제 사용할 수 있는지 간단하게 짚고 넘어가기로 한다. 물론 다른 카테고리의 문제에도 나오지 말라는 법은 없지만 이 테크닉을 가장 많이 사용하게 되는 분야는 역시 트리이다. (사실은 선형 구조여도 비슷한 — 집합을 합치는 — 상황이 되면 써야 편해지는데 선형 구조에서 그런 상황이 나오는 문제가 많지 않은 것 같다.) 자식 노드들에서 뭔가를 처리하고 그걸 바탕으로 부모 노드를 처리하거나, 아니면 간선이 추가될 때마다 뭔가를 처리해야 하는데 이 과정에서 집합을 합쳐야 하는 경우 스몰 투 라지 테크닉을 적용하여 문제를 해결할 수 있다. 이 글에 소개된 연습문제들도 전부 트리와 관련된 문제임을 알 수 있다.

 

구현은 다음과 같다. 큰 집합을 그대로 두고 작은 집합만 합치면서 큰 집합에 빠르게 접근할 수 있게 하는 부분을 주의하자.

#import<bits/stdc++.h>
using namespace std;
int p[100005]; // i번 집합이 S[p[i]]에 존재함
set<int>S[100005];
void _merge(int x, int y) // y번 집합을 x번 집합에 합친다.
{
    if(S[p[x]].size() > S[p[y]].size())
    {
        S[p[x]].insert(S[p[y]].begin(), S[p[y]].end());
        S[p[y]].clear();
    }
    else
    {
        S[p[y]].insert(S[p[x]].begin(), S[p[x]].end());
        S[p[x]].clear();
        swap(p[x], p[y]); // 큰 집합을 작은 집합에 합쳐야 하는 경우 일단 작은 집합을 큰 집합에 합치고 포인터를 맞바꾼다.
    }
}
int main()
{
    int k, n, x;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> k;
        for(int j = 1; j <= k; j++)
        {
            cin >> x;
            S[i].insert(x);
        }
    }
    iota(p, p + n + 1, 0);
}

_merge 함수는 분리 집합 글에 나온 _union, _find 함수와 비슷하게 std::merge 등과 식별자가 충돌할 가능성이 있기 때문에 앞에 언더바가 붙었다. 

 

[연습문제]

 

BOJ 28277. 뭉쳐야 산다 (Platinum V)

오랫동안 백준에 스몰 투 라지 기본 문제라고 부를 만한 문제가 없어서 늦게 만들어진 문제이다. set $N$개를 스몰 투 라지 기법으로 합친다.

 

BOJ 17469. 트리의 색깔과 쿼리 (Platinum III)

이 문제를 조금 더 응용한 것으로 볼 수 있다. 모든 정점이 분리된 마지막 상태에서 시작해서 쿼리를 거꾸로 처리하는 방법이 서로 유사하며, 여기에 분리 집합을 추가해서 연결된 정점들의 색 집합을 관리하면 문제를 풀 수 있다.

 

BOJ 28296. 물류창고 (Platinum III)

이번에는 그래프에서 최대  스패닝 트리를 찾으면서 문제를 풀게 된다. 이동 상한선이 큰 도로부터 확인하면서 두 물류창고가 연결될 때마다 그 도로의 이동 상한선이 배송 상한선이 되는 같은 회사끼리의 물류창고의 쌍의 수를 세서 다 더하면 된다. map 등을 이용하면 구현이 수월할 것이다.

 

BOJ 25549. 트리의 MEX (Platinum III)

리프 노드부터 차례로 정점의 MEX를 구하면 된다. 노드의 MEX보다 크면서 서브트리에서 등장하는 값들, 즉 이후에 MEX 판별에 사용될지도 모르는 값들을 set으로 관리한다. 자식 노드들의 MEX 값과 현재 노드의 값, 그리고 관리하는 set을 이용해여 현재 노드의 MEX 값을 구할 수 있다.

 

→ solved.ac tag: smaller_to_larger

---

1. 한국어로도 저걸 다 읽으면 길기 때문에 그냥 스몰 투 라지, 아니면 아예 작은거 큰거라고 부르는 경우가 많다. [본문으로]