서로소 집합 자료 구조 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Dsu disjoint sets init.svg|섬네일|360px|''메이크셋''은 8개의 개체를 생성한다.]]
[[파일:Dsu disjoint sets final.svg|섬네일|360px|''유니온'' 연산을 여러 번 수행하면 여러 집합들이 합쳐진다.]]

[[컴퓨터 과학]] 분야에서 '''서로소 집합'''(disjoint-set) 자료 구조, 또는 '''합집합-찾기'''(union–find) 자료 구조, '''병합-찾기 집합'''(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 [[자료 구조]]이다. 서로소 집합 자료 구조는 두 개의 유용한 연산을 제공한다:

* ''파인드(Find)'': 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. ''파인드''는 일반적으로 어떤 원소가 속한 집합을 "대표" 하는 원소를 반환하는데, 이를 위하여 어떤 원소와 각 대표 원소들 간의 ''파인드'' 결과를 비교하여 같은 집합임을 판단한다.

* ''유니온(Union)'': 두 개의 집합을 하나의 집합으로 합친다.

다른 중요한 연산으로 ''메이크셋''(MakeSet)이 있으며 이는 특정 한 원소만을 가지는 집합을 만든다. 이 세 연산을 활용하여 많은 파티션(partitioning) 문제들을 해결할 수 있다. (''응용'' 부분 참조)

위의 연산들을 정의하기 위하여 집합을 표현하는 방법이 필요하다. 일반적으로 각 집합 전체를 대표하는 하나의 고정된 ''대표 원소''를 정하는 방법이 있다. 이 방법에서 ''파인드''(x) 연산은 원소 ''x''가 속한 집합의 대표 원소를 반환하고 ''유니온'' 연산은 두 대표 원소를 입력 인자로 사용한다.

== 서로소 집합 연결 리스트 (Disjoint-set linked lists) ==
서로소 집합 데이터 구조는 간단히 각 집합을 표현하기 위하여 [[연결 리스트]](linked list)를 사용한다. 각 리스트의 헤드(head) 부분에는 해당 집합의 대표 원소를 저장한다.

''MakeSet''은 한 원소만을 가지는 리스트를 생성한다. ''유니온''은 두 리스트를 붙이는 연산을 수행하며, 이때 한 리스트의 헤드 부분이 다른 리스트의 꼬리를 가리켜 상수-시간(constant-time) 연산을 수행한다. ''파인드'' 연산시 특정 원소로부터 리스트의 헤드까지 반대 방향으로 탐사해야 하며, 그렇기 때문에 선형 시간(linear time) 또는 [[Big-O notation|O]](''n'') 시간을 요구한다는 단점을 가진다.

이 단점은 각 연결 리스트 노드에 헤드를 가리키는 포인터를 포함시켜 해결할 수 있다.
이 포인터를 통하여 직접적으로 대표 원소를 참조 할 수 있으며, 그 때문에 ''파인드'' 연산은 상수 시간이 걸린다. 그러나 이 경우 ''유니온'' 연산시 덧붙여지는 각 원소들이 새로운 리스트의 헤드를 가리키도록 갱신해야하기 때문에 [[Big-O notation|O]](''n'') 시간을 요구하게 된다.

만약 각 리스트의 길이를 추적 할 수 있다면, 항상 짧은 리스트를 긴 리스트에 덧붙이면서 요구 시간(required time) 성능을 향상시킬 수 있다. 이 방법은 ''가중치-유니온 휴리스틱''(weighted-union heuristic) 라 불리며, ''n''개의 원소들의 ''m''개의 연이은 ''메이크셋'', ''유니온'', 그리고 ''파인드'' 연산을 수행할 경우 O(''m''&nbsp;+&nbsp;''n''log&nbsp;''n'') 시간을 요구한다.<ref name="IntroductionToAlgorithms">{{인용|first1=Thomas H. |last1=Cormen |author1-link=Thomas H. Cormen |first2=Charles E. |last2=Leiserson |author2-link=Charles E. Leiserson |first3=Ronald L. |last3=Rivest |author3-link=Ronald L. Rivest |first4=Clifford |last4=Stein |author4-link=Clifford Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press |year=2001 |isbn=0-262-03293-7 |chapter=Chapter 21: Data structures for Disjoint Sets |pages=498–524 }}</ref> 점근적으로(asymptotically) 더 빠른 연산을 위해서 다른 자료 구조가 필요하다.


=== 단순한 접근법 분석 ===
지금부터 위 연산이 <math>O(n \log(n))</math> 제한을 갖는다는 것을 설명하겠다.

만약 여러 리스트들이 있고 각 리스트의 노드들은 속한 리스트의 이름과 원소의 개수 정보를 저장하는 객체를 포함한다고 가정하다. 그리고 모든 리스트들의 전체 원소 개수가 <math>n</math> 개 있다고 가정하자. 이 리스트들 중에 어느 두 개의 리스트를 병합하고, 각 리스트들이 속한 리스트 이름이 유지되도록 노드의 업데이트 하려고 한다. 만약 리스트 <math>A</math>의 길이가 리스트 B보다 길 경우 병합하는 규칙은 <math>B</math>의 원소들을 <math>A</math> 안으로 병합 후 <math>B</math>에 속했던 원소들의 정보를 갱신하는 것이다.

리스트 <math>L</math>에서 특정 원소 <math>x</math>를 정하자. 우리는 최악의 경우 얼마나 많이 <math>x</math>는 속한 리스트의 이름을 갱신하는지 계산 하려고 한다. 원소 <math>x</math>가 속한 리스트의 길이보다 길거나 같은 리스트와 병합을 할 때 <math>x</math>는 속한 리스트 이름을 갱신한다. 갱신이 일어날 때마다 <math>x</math>가 속한 리스트의 크기는 최소 두 배 이상 증가한다. 그러므로 질문은 다음과 같다. “크기가 n이기 이전에 얼마나 자주 숫자가 두 배가 되는가?” (그러면 <math>x</math>를 포함하는 리스트는 모든 <math>n</math>개의 요소들을 포함할 것이다). 답은 정확히 <math>\log_2(n)</math>이다. 그래서 특정 리스트 안의 특정 한 원소는 최악의 경우 <math>\log_2(n)</math> 번의 갱신이 필요할 것이다. 그러므로 <math>n</math>개의 원소를 가지는 한 리스트는 최악의 경우 <math>O(n \log(n))</math> 시간이 걸린다. 이 구조에서 각 노드는 원소가 속한 리스트의 이름을 포함하기 때문에, 파인드 연산은 <math>O(1)</math> 시간이 걸린다.

마찬가지로 위의 주장은 트리 자료구조의 병합에도 유의하며 다음 장에서 기술하였다.
추가적으로 이는 [[이진 힙]](binomial heap) 과 [[피보나치 힙]](Fibonacci heap) 자료구조에서 여러 가지 연산들의 시간을 분석하는데 활용된다.

== 서로소 집합 숲 (Disjoint-set forest) ==

서로소 집합 숲(Disjoint-set forest)는 각 집합이 트리로 표현되는 자료구조이며 각 노드들은 부모 노드를 참조한다. 이 구조는 1964년 Bernard A. Galler와 Michael J. Fischer가 처음으로 고안하였으며<ref>{{인용|first=Bernard A. |last=Galler |author1-link=Bernard A. Galler |first2=Michael J. |last2=Fischer |author2-link=Michael J. Fischer |title=An improved equivalence algorithm |journal=[[Communications of the ACM]] |volume=7 |issue=5 |date=May 1964 |pages=301–303 |url=http://portal.acm.org/citation.cfm?doid=364099.364331 |doi=10.1145/364099.364331}}. The paper originating disjoint-set forests.</ref>, 이후 정밀한 분석은 수년이 걸렸다.
서로소 집합 숲에서 각 집합의 대표는 해당 트리의 루트(root) 노드이다. ''파인드'' 연산은 특정 노드에서 루트 노드에 도달할 때까지 부모 노드를 따라 참조한다. ''유니온''은 두 개의 트리를 하나로 병합하는 연산으로 한 루트 노드를 다른 루트 노드에 연결한다.
이 단순한 서로소 집합 숲 방법은 매우 불균형적인 트리를 생성 할 수 있기 때문에, 연결 리스트 방법과 다를 바 없다.


=== 구현 ===

==== 단순한 형태 ====
위의 연산들의 구현은 아래와 같다:

  '''function''' ''MakeSet''(x)
      x.parent := x

  '''function''' ''Find''(x)
      if x.parent == x
         return x
      else
         return ''Find''(x.parent)

  '''function''' ''Union''(x, y)
      xRoot := ''Find''(x)
      yRoot := ''Find''(y)
      xRoot.parent := yRoot

단순한 형태의 연산들은 매우 불균형적인 트리를 생성하기 때문에 성능 측면에서 연결 리스트 방법과 다를 바 없다.

==== 유니온 바이 랭크(Union by rank) ====

다음 두 방법으로 위 방법의 성능을 향상시킬 수 있다.

첫 번째는 ''유니온 바이 랭크''(union by rank) 방법으로 항상 작은 트리를 큰 트리 루트에 붙이는 방법이다. 트리의 깊이(depth)가 실행 시간에 영향을 주기 때문에, 깊이가 적은 트리를 깊이가 더 깊은 트리의 루트 아래에 추가한다. 그러면 두 트리의 깊이가 같을 경우에만 깊이가 증가한다. 만약 ''경로 압축''(path compression)을 활용 한다면 깊이가 같을 경우 알고리즘 동작이 멈추기 때문에 깊이 대신 ''랭크''(rank)라는 용어를 사용한다. 한 개의 원소를 가지는 트리는 랭크 ''0''을 가지고, 같은 랭크 ''r''을 가지는 두 트리가 합쳐질 경우 랭크 ''r''+1의 트리가 만들어진다. 이 기술을 활용하여 ''유니온'' 또는 ''파인드'' 연산은 최악의 경우 {{math|''O''(log ''n'')}} 실행 시간을 가진다. 향상된 ''메이크셋''과 ''유니온'' 연산의 의사코드는 다음과 같다:

  '''function''' ''MakeSet''(x)
      x.parent := x
      x.rank   := 0

  '''function''' ''Union''(x, y)
      xRoot := ''Find''(x)
      yRoot := ''Find''(y)
      // if x and y are already in the same set (i.e., have the same root or representative)
      if xRoot == yRoot
          return

      // x and y are not in same set, so we merge them
      if xRoot.rank < yRoot.rank
          xRoot.parent := yRoot
      else if xRoot.rank > yRoot.rank
          yRoot.parent := xRoot
      else
          yRoot.parent := xRoot
          xRoot.rank := xRoot.rank + 1

==== 경로 압축 ====

두 번째 방법은 ''경로 압축''(path compression)으로 ''파인드'' 연산을 수행할 때마다 트리의 구조를 평평하게 만드는 방법이다. 이 방법은 루트 노드까지 순회중 방문한 각 노드들이 직접 루트 노드를 가리키도록 갱신하는 것으로, 모든 노드들은 같은 대표 노드를 공유하게 된다. 트리 윗부분을 재귀적으로 순회하면서 각 노드들이 루트 노드를 부모 노드로 참조하도록 갱신한다.
최종적으로 생성된 트리는 보다 평평하며, 이는 해당 원소뿐만 아니라 이들을 직/간접적으로 참조하는 연산들의 속도를 빠르게 해준다. 다음은 향상된 ''파인드'' 연산이다:

  '''function''' ''Find''(x)
      if x.parent != x
         x.parent := ''Find''(x.parent)
      return x.parent

이 두 기술들은 상호 보완 및 적용 가능하며, 각 연산마다 [[분할상환 시간]](amortized time)은 단지<math>O(\alpha(n))</math>이며 여기서 <math>\alpha(n)</math>는 함수 <math>n = f(x) = A(x,x)</math>의 역 함수이다. (<math>A</math>는 극도로 빠르게 성장하는 [[아커만 함수]] (Ackermann function)이다. <math>\alpha(n)</math>는 이 함수의 역함수이기 때문에, <math>\alpha(n)</math>는 <math>n</math>의 모든 원격 실용적인 값(remotely practical value)으로 5보다 작다.

실제로 이는 [[점근적 최적값]](asymptotically optimal)이다: Fredman 과 Saks는 1989년에 서로소 집합 자료구조의 각 연산마다 <math>\Omega(\alpha(n))</math> 단어들을 접근 할 수 있다고 보였다.<ref>{{인용|first=M. |last=Fredman |authorlink=Michael Fredman |first2=M. |last2=Saks |title=The cell probe complexity of dynamic data structures |journal=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing |pages=345–354 |date=May 1989 |quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires Ω(''m'' α(''m'', ''n'')) time to execute ''m'' Find's and ''n''−1 Union's, beginning with ''n'' singleton sets. }}</ref>


== 응용 ==

[[파일:UnionFindKruskalDemo.gif|250px|섬네일|크루스칼( Kruskal) 알고리즘을 활용하여 최소 스패닝 트리(minimum spanning tree)를 찾을 때 유니온-파인드(Union-Find) 연산의 데모]]

서로소 집합 자료구조는 집합의 분할을 모델링한다. 예를 들어 이 자료구조를 활용하여 [[무향 그래프]](undirected graph)의 연결된 요소들을 추적 할 수 있다. 그리고 이 모델은 두 개의 꼭짓점(vertex)들이 같은 요소에 속하는지 또는 그 꼭짓점들을 엣지(edge)로 연결할 때 싸이클(cycle)이 발생하는지 등을 결정 할 수 있다. 유니온-파인드 알고리즘은 고성능 단일화(unification)의 구현에 활용된다.<ref>{{저널 인용|last1=Knight |first1=Kevin|year=1989 |title=Unification: A multidisciplinary survey |journal=ACM Computing Surveys|pages=93–124 |url=http://portal.acm.org/citation.cfm?id=62030|doi=10.1145/62029.62030 |volume=21}}</ref>

이 데이터 구조는 점진적으로 연결된 요소([https://web.archive.org/web/20081012154946/http://boost.org/libs/graph/doc/incremental_components.html Incremental Connected Components]) 기능을 구현하기 위하여 [[Boost Graph Library]]에서 활용하고 있다. 또한 크루스칼(Kruskal) 알고리즘에서 그래프의 [[최소 신장 트리]](minimum spanning tree)를 찾는데 활용된다.

위의 서로소 집합 숲 구현은 엣지의 삭제는 지원하지 않는다(심지어 경로 압축 또는 랭크 휴리스틱(rank heuristic)이 없이도).

== 역사 ==

서로소 집합 숲에 사용된 아이디어는 오랫동안 익숙하지만, Robert Tarjan은 1975년 처음으로 역 아커만 함수에 관하여 상한(upper bound)을 증명하였다.<ref>{{저널 인용|last1=Tarjan |first1=Robert Endre |author1-link=Robert E. Tarjan |year=1975 |title=Efficiency of a Good But Not Linear Set Union Algorithm |journal=Journal of the ACM |volume=22 |issue=2 |pages=215–225 |url=http://portal.acm.org/citation.cfm?id=321884 |doi=10.1145/321879.321884 }}</ref> 이때까지 각 연산별 시간에 대하여 최적 경계(best bound)는 O(log* n)이고 (Hopcroft와 Ullman가 증명<ref>{{저널 인용|last1=Hopcroft |first1=J. E. |author1-link=John Hopcroft |last2=Ullman |first2=J. D. |author2-link=Jeffrey Ullman |year=1973 |title=Set Merging Algorithms |journal=SIAM Journal on Computing |volume=2 |issue=4 |pages=294–303 |doi=10.1137/0202024}}</ref>) 여기서 n은 알고리즘의 반복 횟수이다. (하지만 역 아커만 함수 보다 그다지 느리지 않다)

Tarjan 과 Van Leeuwen은 최악 경우 복잡도(worst-case complexity)는 유지하면서 실제 더 효율적인 한 경로(one-pass) ''파인드'' 알고리즘을 개발 하였다.<ref>{{인용|first=Robert E. |last=Tarjan |author1-link=Robert E. Tarjan |first2=Jan |last2=van Leeuwen |author2-link=Jan van Leeuwen |title=Worst-case analysis of set union algorithms |journal=Journal of the ACM |volume=31 |issue=2 |pages=245–281 |year=1984 |doi= 10.1145/62.2160}}</ref>

2007년에는 Sylvain Conchon과 Jean-Christophe Filliâtre은 서로소 집합 숲 자료구조의 지속 버전을 개발하였다. 이는 Coq의 증명을 활용하여 이전 버전의 구조는 효율적으로 유지하고 정확성을 형식화한 버전이다.<ref>{{인용|first=Sylvain |last=Conchon |first2=Jean-Christophe |last2=Filliâtre |contribution=A Persistent Union-Find Data Structure |title=ACM SIGPLAN Workshop on ML |location=Freiburg, Germany |date=October 2007|url=https://www.lri.fr/~filliatr/puf/}}</ref>


== 각주 ==
{{각주|30em}}

== 외부 링크 ==
* [https://web.archive.org/web/20071108172118/http://www.boost.org/libs/disjoint_sets/disjoint_sets.html C++ implementation], part of the [[Boost|Boost C++ libraries]]
* [https://web.archive.org/web/20170225172246/http://www.lix.polytechnique.fr/~nielsen/Srmjava.java A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)]
* [http://www.cs.unm.edu/~rlpm/499/uf.html Java applet: A Graphical Union–Find Implementation], by Rory L. P. McGuire
* ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.8354 Wait-free Parallel Algorithms for the Union–Find Problem]'', a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union–Find that never needs to block
* [http://code.activestate.com/recipes/215912-union-find-data-structure/ Python implementation]
* [https://web.archive.org/web/20161202120715/http://www.mathblog.dk/disjoint-set-data-structure/ Visual explanation and C# code]

[[분류:자료 구조]]
[[분류:검색 알고리즘]]
[[분류:분할 상환 자료 구조]]