집합

상호배타적 집합이란?

교집합이 없는 집합 관계를 말합니다.

집합 A와 B의 원소는 겹치는 경우가 없습니다. 이를 우리는 상호 베타적 집합이라고 할 수 있습니다.

위와 같이 중복된 3을 갖고 있을 경우 상호 배타적 집합이 아니라고 합니다.

대표원소란?

대표 원소는 집합의 원소 중 집합을 대표하는 역할을 합니다. 집합의 형태를 트리로 표현하므로 루트 노드라고 합니다.

배열로 집합을 표현하는 것이란?

집합을 배열로 표현한다는 것은 하나의 배열로 상호 베타적 관계를 가지는 집합을 모두 표현한다는 것을 의미합니다.

배열의 인덱스는 자신을 배열 값은 부모 노드를 의미합니다.

예를 들어 Array[3] = 9면 노드 3의 부몬 노드는 9임을 나타냅니다. 루트노드는 말 그대로 집합의 대표 이미르 보모가 없고 부모 노드가 자기 자신이 되는 것입니다.

위 배열을 보았을 때 2를 가리키는 5와 7은 2의 자식이고 2는 스스로를 가리키니 해당 인덱스는 루트 노드를 가리키는 것을 볼 수 있습니다.

파인드 연산

특정 노드의 루트 노드가 무엇인지 탐색하는 방법입니다. 보통 파인드 연산은 특정 노드가 같은 집합에 있는지 확인할 때 사용합니다.

1. 현재 노드의 부모 노드를 확인합니다. 부모 노드를 확인하다가 부모 노드가 루트 노드이면 찾기 연산을 종료합니다.

2. 1에서 찾기 연산이 종료되지 않으면 1을 반복합니다.

해당 연산의 경우 시간 복잡도는 을 유지합니다. 이를 개선하기 위해 경로 압축을 활용할 수 있습니다.

파인드 연산의 연산 비용 문제, 경로 압축으로 해결

이를 위해서 우리는 집합 형태를 유지하면서 트리 높이를 줄이는 방향으로 가면 됩니다. 트리의 높이를 줄이므로 앞서 언급한 부모 노드를 거치는 과정을 줄일 수 있습니다.

유니온 연산

유니온 연산은 두 집합을 하나로 합치는 연산입니다. '두 집합을 합친다'는 것은 두 집합의 루트 노드를 같게 하는 것입니다.

1. 두 집합에서 찾기 연산을 통해 루트 노드를 찾습니다.

2. 찾은 두 루트 노드의 값을 비교합니다.

3. 두 집합을 합칩니다. 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관 없습니다.

유니온 연산의 연산 비용 문제, 랭크로 해결하자.

트리의 깊이가 깊어지면 깊어질수록 연산 비용이 커진다는 단점이 있습니다. 때문에 랭크를 도입합니다.

랭크란?

현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말합니다.

랭크 기반으로 합치기 연산하기

1. 두 노드의 루트 노드를 구합니다.

2. 구한 노드의 랭크를 비교합니다.

3. 랭크 값이 다르면 랭크 값이 더 큰 루트 노드를 기준으로 삼습니다.

4. 랭크 값이 같다면 아무거나 선택해서 바꾸고 루트 노드의 랭크를 1을 더합니다.