mir.pe (일반/밝은 화면)
최근 수정 시각 : 2021-11-13 15:11:44

Union Find



''' 이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		<colbgcolor=#aa3366> 이론
기본 대상 수학기초론{ 수리논리학( 논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학( 그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 FSM · 푸시다운 · 튜링 머신( 폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
계산 복잡도 이론 점근 표기법 · 튜링 기계^ 고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임( 그리디 알고리즘, 동적 계획법)
정보이론 데이터 압축( 무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론 프로그래밍 언어( 함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현 배열^ 벡터^ · 리스트^ 연결 리스트^ · 셋(set)^ 레드-블랙 트리, B-트리^ · 우선순위 큐^ 힙, 피보나치 힙^
수학적 최적화 조합 최적화 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시( MD5 · 암호화폐 · 사전 공격( 레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식 블록 암호 알고리즘( AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식 공개키 암호 알고리즘( 타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^ BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제 대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 }}}}}}}}}



1. 개요2. 설명
2.1. 원시적 형태2.2. 기본적 형태
2.2.1. Find 연산
2.2.1.1. Find 연산의 최적화
2.2.2. Union 연산
2.2.2.1. Union 연산의 최적화
3. 구현

1. 개요

Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조이다. 이 자료구조가 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단하는 Find 연산을 지원하기 때문에 Union-Find라는 이름이 붙게 되었다. 1964년 처음 고안되었다. 크러스컬 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다.

2. 설명

2.1. 원시적 형태

ArrayList에 상호 배타적 집합을 표현하기 위한 가장 간단한 방법은 배열의 각 요소에 집합의 고유 번호를 넣는 것이다. 이렇게 될 경우, 배열의 원소에 접근하는 것 만으로 속한 집합을 알 수 있게 되므로 Find 연산은 항상 [math( O(1) )]의 시간복잡도를 가지게 된다. 그러므로 효율적이라고 할 수 있다. 그러나 Union 연산을 수행하기 위해서는 ArrayList의 모든 원소를 순회하며 각 원소가 속한 집합의 고유 번호를 바꿔 주어야 하므로 항상 [math( O(n) )]의 시간복잡도를 가지는 것을 알 수 있다. 선형 시간이 걸리는 이 문제를, 트리 형태로 집합을 표현함으로써 해결할 수 있다.

2.2. 기본적 형태

Disjoint Set에서는 트리를 특이한 용도로 사용하는데, 트리의 구조 자체가 의미를 가지는 경우가 많은 반면 Disjoint Set에서는 트리의 구조와는 상관 없이 단 하나의 최상위 노드에만 관심을 가진다. Disjoint Set의 트리 구조에서 최상위 노드는 각 집합을 대표하는 대표자 역할을 맡게 된다. Disjoint Set을 트리로 표현하기 위해서는 먼저 ArrayList의 각 원소에 자신의 인덱스 값이 들어가 있는 초기 상태가 필요하다. 이 상태에서 각 원소에 들어가 있는 값은 각 원소의 부모를 의미한다.

2.2.1. Find 연산

Find 연산이 수행되면, 재귀적으로 트리를 거슬러 올라가 최상위 노드의 값을 반환한다. 트리 형태로 구현된 Disjoint Set에서 최상위 노드는 각 집합과 1대 1 대응되므로, Find 연산을 통해 각 집합을 알 수 있게 된다. 이 과정에서 상수 시간에 가까운 정도의 시간이 걸린다고 알려져 있다.
2.2.1.1. Find 연산의 최적화
Find 연산을 수행할 때마다 매번 트리를 거슬러 올라가는 것은 분명히 낭비이다. 만약 트리의 원소가 편중되어 있다면, 시간복잡도는 [math( O(n) )]에 근접하게 된다. 이를 보완하기 위해서, Find 연산에서 방문하는 각 노드마다 결과값을 반환하기 전에 ArrayList의 해당 원소의 값을 결과값으로 저장한다. 이렇게 하면 경로를 압축하는 효과가 있다.

2.2.2. Union 연산

Union 연산이 수행되면, 먼저 Find 연산을 수행한 후 두 개의 최상위 노드의 부모를 다른 하나의 최상위 노드로 바꾸어 트리를 병합시킨다. 이 과정에서 시간에 영향을 미치는 것은 Find 연산 뿐이므로, 시간복잡도는 Find 연산과 동일하다는 것을 알 수 있다.
2.2.2.1. Union 연산의 최적화
Union 연산은 최악의 경우에 트리를 편중시킬 수 있다는 문제를 가지고 있다. 이를 해결하기 위해, ArrayList를 하나 더 만들어서 트리의 대략적인 깊이를 저장한다. 이것을 rank라고 한다. Union 연산을 수행할 때는 rank가 큰 트리에 rank가 작은 트리를 합치도록 변경하면 트리의 깊이를 줄이는 효과가 있다.

3. 구현

#!syntax python
    ArrayList list = []

    Function additem():
        list.append([list.length, 0])

    Function find(index):
        if list[index][0] == index:
            return index
        else:
            return find(list[index][0])

    Function union(a, b):
        roota = self.find(a)
        rootb = self.find(b)
        list[roota][0] = list[rootb][0]

분류