초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
컴퓨터 여덟 대를 케이블로 하나씩 잇는다고 합시다. 케이블을 이을 때마다 1번과 7번 컴퓨터 사이에 데이터가 오갈 수 있는지 묻고 싶습니다. 케이블로 이어진 컴퓨터들을 한 무리로 보면, 할 일은 두 무리를 합치기(union)와 두 컴퓨터가 같은 무리인지 찾기(find) 둘입니다.
컴퓨터마다 무리 번호를 배열에 적어 두면 찾기는 번호 두 개만 비교하면 됩니다. 하지만 합칠 때는 한쪽 무리의 컴퓨터를 모두 찾아 번호를 고쳐야 합니다. 배열 전체를 훑으니 컴퓨터가 n대면 O(n)입니다.
번호 대신 컴퓨터마다 부모 하나만 적어 둡시다. 그러면 무리마다 트리가 하나 생기고, 루트가 그 무리의 대표입니다. 지금까지의 트리와 달리 자식이 부모를 가리키고, 루트는 자기 자신을 부모로 적습니다.
이렇게 원소들을 무리로 나눠 두고 합치기와 찾기를 하는 자료구조를 유니온 파인드(union-find)라 합니다.
원소 두 개를 골라 합치거나 찾아봅시다.
하이라이트된 노드가 대표, 굵은 테두리가 찾으며 지나온 노드입니다. 이 데모는 a의 대표를 b의 대표 아래에 답니다.
같은 순서를 C로 옮기면 다음과 같습니다.
출력 없음재생하며 parent에서 바뀌는 칸을 봅시다.
합치는 순서가 나쁘면 트리가 한 줄로 늘어서 찾기가 O(n)이 됩니다. 두 가지 방법으로 막습니다.
원소 두 개를 골라 합치거나 찾아봅시다.
둘을 함께 쓰면 연산을 여러 번 할 때 한 번에 걸리는 시간이 평균적으로 거의 상수입니다. 1975년 타잔(Robert Tarjan)은 이 시간이 느리게 자라는 함수 α(n)에 비례함을 밝혔습니다. α(n)은 현실에서 다룰 어떤 n에서도 4를 넘지 않습니다.
이번 파트에서는 값을 갈래로 뻗게 담는 트리를 다뤘습니다. 트리는 위아래 관계를 담고, 이진 탐색 트리와 AVL 트리는 순서를 지키며 층 수만큼만 비교해 찾고 넣습니다. 힙은 가장 작은 값을 늘 루트에 두고, 유니온 파인드는 무리를 합치고 찾는 일을 거의 상수 시간에 합니다. 그런데 이진 탐색처럼 정렬된 데이터를 쓰려면 먼저 정렬해야 하고, 알고리즘 글의 선택 정렬은 O(n²)입니다. 정해진 풀이 없이 경우를 하나씩 만들어 봐야 하는 문제도 있습니다. 그래서 다음 파트에서는 문제를 다 해 보거나 작게 쪼개서 푸는 방법을 다룹니다. 첫 글은 재귀입니다.
원소 1000개가 처음에 모두 따로 있습니다. 경로 압축 없이 크기 합치기만 쓰며 합치기를 원하는 만큼 합니다. 크기가 같은 두 트리를 합칠 때는 어느 쪽을 아래에 달아도 됩니다. 그 뒤 찾기 한 번에 부모를 따라 올라가는 횟수는 가장 많을 때 몇 번일까요? 숫자로 답하세요.