| '''이론 컴퓨터 과학 {{{#!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. 개요
Union-Find(혹은 Disjoint Set)은 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조이다. 이 자료구조가 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단하는 Find 연산을 지원하기 때문에 Union-Find라는 이름이 붙게 되었다. 1964년 처음 고안되었다. 크러스컬 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다.2. 설명
- Find 연산은 하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산을 말한다.
- Union 연산은 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집합 연산과 동치이다.
- [math(n)]은 모든 원소의 개수로 한다.
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]