🌌 집합이란?
집합(Set)은 순서와 중복이 없는 원소들을 갖는 자료구조를 말한다. 예를 들어 어떤 A라는 그룹의 원소 구성이 {1,6,6,6,4,3}이면 이는 중복을 제외해 {1,6,4,3}으로 생각해야 한다. 순서는 따로 따지지 않으니 {6,1,3,4}와 같이 생각해도 된다.
집합의 종류
집합은 특성에 따라 부르는 말이 다양하다. 원소 개수가 유한한 유한 집합, 무한한 무한 집합, 아무런 원소도 없는 공집합 등 여러 집합이 있지만 여기에서는 상호배타적 집합에 집중해서 설명하도록 하겠다.
상호배타적 집합이란?
상호배타적 집합은 교집합이 없는 집합 관계를 말한다.
A = {1,2,3}
B = {4,5,6,7}위 그림처럼 두 집합이 있을 때, 집합 A와 B는 겹치는 원소가 없으므로 상호배타적 집합이다.
A = {1,5,3}
B = {4,5,6,7}반대로 이런 케이스에서는 A와 B는 상호배타적 집합으로 치부할 수 없다. 집합 A의 원소 5가 집합 B에도 있기 때문이다.
상호배타적 집합의 특성을 활용하는 분야
코딩 테스트에서 상호배타적 집합을 배워야 하는 가장 현실적인 이유는 그래프 알고리즘에서 많이 활용하기 때문이다. 그래프 알고리즘은 추후 따로 다루겠지만 흔히 사이클을 확인하는 일이 많은데, 그 작업에서 상호배타적 집합 개념을 활용한다. 이 외에도 상호배타적 집합 개념을 활용하는 알고리즘은 다양하다.
-
이미지 분할: 이미지를 서로 다룬 부분으로 나누는 데 사용한다. 예를 들어 사람과 배경을 겹치지 않게 분할하는 데 사용될 수 있다.
-
도로 네트워크 구성: 도로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는 데 사용될 수 있다. 이를 통해 교차로의 혼잡을 줄인다.
-
최소 신장 트리 알고리즘 구현: 최소 신장 트리 알고리즘 구현에서 간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용한다.
-
게임 개발: 캐릭터의 동작을 자연스럽게 구현할 수 있다. 예를 들어 플레이어와 적군이 충돌할 때 이 두 캐릭터가 겹치지 않도록 하는 데 사용할 수 있다.
-
클러스터링 작업: 각 작업이 서로 겹치지 않도록 구성할 수 있다. 이렇게 작업 간의 의존 관계가 없으면 동시에 여러 작업을 진행할 수 있다.
🎨 집합 표현하기
이제 집합을 표현하는 방법과 관련 연산들을 알아보자. 보통 집합은 트리로 표현하며 대표적인 연산은 합치기와 탐색이 있다. 순서대로 알아보자.
배열을 활용한 트리로 집합 표현하기
집합은 배열을 활용한 트리로 구현된다. 각 집합에는 대표 원소가 있어야 하므로 대표 원소가 무엇인지부터 알아보자.
대표 원소란?
대표 원소는 집합의 원소 중 집합을 대표하는 역할을 한다. 다만 이 방법에서는 집합의 형태를 트리로 표현할 것이므로 대표 원소는 루트 노드라고 부른다.
※ 개념적으로 집합의 대표 원소와 트리의 루트 노드는 같다.
배열로 집합을 표현하는 것이란?
집합을 배열로 표현한다는 것은 하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다는 것을 의미한다. 그리고 집합을 트리 형태로 표현할 때는 다음을 기억하면 된다.
- 배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.
예를 들어 disjoint_set[3] = 9면 노드 3의 부모 노드는 9임을 의미한다. 루트 노드는 말 그대로 집합의 대표이므로 부모가 없고, 부모 노드가 자기 자신이다. 다시 말해 루트 노드는 값 자체가 배열의 인덱스와 동일하다.
집합을 표현하는 데 사용되는 배열의 크기:
max(disjoint_set) + 1
그렇다면 집합을 표현하는 데 사용되는 배열의 크기는 어때야 할까? 배열의 인덱스가 모든 집합의 원소를 표현할 수 있으면 된다. 예를 들어 위 그림은 값이 가장 큰 원소가 9이므로 배열의 크기는 10으로 잡는다. 왜냐하면 배열의 인덱스는 0부터 시작하지만, 보통 집합에서 0은 잘 사용하지 않기 때문이다.
집합 표현 완벽 정리
이제 다른 예를 보며 집합 개념을 정리해 보도록 하겠다. 아래 그림을 보자. 위와 같은 집합을 앞서 본 것처럼 disjoint_set 배열을 활용한 트리로 나타내면 다음 특성을 가지게 된다.
-
각 집합의 루트 노드는 1과 4
disjoint_set배열에 표현하면disjoint_set[1] = 1,disjoint_set[4] = 4이다.
-
disjoint_set[3] = 2,disjoint_set[2] = 1- 해석해보면 집합 A의 원소 3의 부모는 2, 집합 B의 원소 2의 부모는 1이란 뜻이다.
- 그리고 원소 3은
disjoint_set[3] = 2,disjoint_set[2] = 1,disjoint_set[1] = 1이므로 원소 3은 원소 1인 루트 노드인 집합에 속한다라고 이야기 할 수 있다.
-
집합 A와 집합 B를 표현할 배열의 크기를 10으로 한다.
-
두 집합은 하나의 배열(
disjoint_set)로 표현할 수 있다.
🧮 집합의 연산
집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다. 보통 합치기는 유니온union, 탐색을 find라고 하므로 둘을 묶어 유니온-파인드union & find 알고리즘이라고 한다.
🔍 파인드(find) 연산
파인드 연산이란, 특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다. 보통 파인드 연산은 특정 노드가 같은 집합에 있는지 확인할 때 사용한다.
예를 들어 A,B 두 노드가 있을 때 이 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것이다. 이 과정을 정리하면 다음과 같다.
- 현재 노드의 부모 노드를 확인 🔍
- 부모 노드가 루트 노드이면 찾기 연산을 종료 🚪
- 찾기 연산이 종료되지 않으면 1을 반복 🔁
이와 같은 탐색 연산은 재귀 함수로 구현한다. 그러나 이 연산은 최악의 경우 시간 복잡도가 O(N)이다. 파인드 연산에서 목표로 하는 것은 루트 노드 찾기이므로 조금은 비효율적인 연산이라고 할 수 있다.
🛤️ 경로 압축
경로 압축(Path Compression)은 파인드 연산의 성능을 최적화하기 위한 기법이다. 파인드 연산은 특정 원소가 속한 집합의 루트 노드를 찾는 연산인데, 경로 압축은 이 과정에서 발생하는 경로를 직접 루트에 연결하여 트리의 높이를 낮추는 방법이다.
경로 압축의 작동 방식
예를 들어, 원소 4가 속한 집합의 루트를 찾기 위해 Find(4) 연산을 호출하면 다음과 같은 과정을 거친다.
- 경로 탐색:
4에서 시작하여 현재 노드의 부모를 따라가면서 루트까지 이동한다. - 경로 압축: 경로 상의 모든 노드의 부모를 직접 루트로 설정한다. 즉,
4에서 시작하여 루트를 찾으면서 동시에4와 경로 상의 모든 노드의 부모를 직접 루트로 변경한다.
이렇게 하면 경로 압축 이후 find(2), find(3), find(4) 연산이 모두 한 번에 수행되어 다음 번에 파인드 연산을 수행할 때 걸리는 시간을 줄일 수 있다.
🤝 합치기 연산
합치기 연산은 두 집합을 하나로 합치는 연산이다. '두 집합을 합친다'는 것은 두 집합의 노드를 같게 하는 것이다. 이때 루트 노드는 두 집합의 루트 노드 중 하나가 되면 된다.
합치기 연산 과정
합치기 연산 과정을 그림으로 표현하면 다음과 같다.
- Find 연산: 두 원소가 속한 집합의 루트를 찾는다. 각 원소의 루트를 찾을 때는 경로 압축(Path Compression)을 사용하여 경로를 최적화한다.
- Union 연산: 두 집합을 합친다.
- 각 집합의 루트를 찾은 후, 두 집합의 루트 노드를 하나로 통일한다.
- 이때 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관 없다.
합치기 연산은 이와 같다. 그러나 이 방식은 조금 생각하면 찾기 연산처럼 트리의 깊이가 깊어지면 깊어질수록 연산 비용이 커진다는 단점이 있다. 이를 개선하려면 랭크라는 개념이 필요하다.
※ 랭크 개념을 도입하는 목적은 '트리의 균형을 유지하기 위함'이다.
📏 랭크
랭크란 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말한다. 이 역시도 그림으로 이해해 보자. 각 노드에 랭크를 표시하면 다음과 같다.
1의 랭크는 노드 4까지의 경로인 2이고, 노드 4,3의 랭크는 0이다.
랭크 기반의 합치기 연산
이제 랭크를 기반으로 합치기 연산을 하는 방법을 알아보자. 랭크 기반의 합치기 연산은 다음과 같은 규칙을 따른다.
-
두 노드의 루트 노드를 구한다:
- 각 노드의 루트를 찾기 위해 파인드 연산을 사용한다.
-
두 루트 노드의 랭크를 비교한다:
-
두 루트 노드의 랭크를 비교하여 다음과 같이 처리한다:
-
2-1. 랭크값이 다른 경우: 랭크가 더 큰 트리(또는 랭크가 큰 루트 노드)를 기준으로 합친다. 즉, 랭크가 작은 트리를 랭크가 큰 트리의 자식으로 만든다. 이렇게 하면 트리의 깊이가 더 깊어지지 않고, 랭크의 값은 변하지 않는다.
-
2-2. 랭크값이 같은 경우: 두 트리의 루트 노드 중 하나를 선택하여 합치고, 선택된 루트 노드의 랭크를 1 증가시킨다. 이 과정은 어느 루트 노드를 선택하더라도 트리의 균형을 유지하며 랭크를 증가시킨다.
-
-
🌐 유니온-파인드 알고리즘 구현
이제 마지막으로 Python 코드를 통해 유니온-파인드 알고리즘을 직접 구현해보자. 구현하기 전 대략적으로 구현 방법을 설명하겠다.
-
초기화: 먼저, 각 원소의 부모를 자기 자신으로 초기화하고, 각 집합의 랭크(트리의 깊이)를 1로 초기화한다.
-
Find연산 (경로 압축 포함):- 특정 원소의 루트 노드(집합의 대표 원소)를 찾는 연산
- 경로 압축을 사용하여 재귀적으로 호출된
Find함수를 통해 루트를 찾는다. - 경로 상의 모든 노드의 부모를 직접 루트로 설정하여 트리의 높이를 줄인다.
-
Union연산 (랭크 기반 합치기):- 두 개의 집합을 하나로 합치는 연산
- 각 집합의 루트를 찾은 후, 두 집합의 랭크(트리의 높이)를 비교하여 더 낮은 트리를 더 높은 트리의 자식으로 만든다.
- 이를 통해 트리의 높이를 낮추어 연산의 효율성을 높인다.
Python 코드
class UnionFind:
def __init__(self, size):
self.parent = list(range(size)) # 각 원소의 부모 노드를 자기 자신으로 초기화
self.rank = [1] * size # 각 집합의 랭크(트리의 깊이)를 1로 초기화
def find(self, p):
if self.parent[p] != p:
self.parent[p] = self.find(self.parent[p]) # 경로 압축(Path Compression)
return self.parent[p]
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p != root_q:
# 랭크 기반 합치기(Union by Rank)
if self.rank[root_p] > self.rank[root_q]:
self.parent[root_q] = root_p
elif self.rank[root_p] < self.rank[root_q]:
self.parent[root_p] = root_q
else:
self.parent[root_q] = root_p
self.rank[root_p] += 1
def connected(self, p, q):
return self.find(p) == self.find(q)코드 설명
-
__init__메서드: 각 원소의 부모를 자기 자신으로 초기화하고, 랭크를 1로 초기화한다. -
find메서드: 특정 원소의 루트 노드(대표 원소)를 찾는 함수로, 경로 압축을 통해 트리의 높이를 최적화한다. -
union메서드: 두 개의 집합을 합치는 함수로, 두 집합의 루트를 찾고 랭크를 기반으로 합치기 연산을 수행한다. -
connected메서드: 두 원소가 같은 집합에 속해 있는지 여부를 판별한다.
마치며
상호배타적 집합과 유니온-파인드 알고리즘은 어려울 수도 있지만 그래프 이론을 포함한 다양한 알고리즘에서 핵심적인 부분을 차지하는 만큼 반드시 알고있어야 한다.
유니온-파인드 알고리즘을 잘 이해하고 구현할 수 있다면, 코딩 테스트에서 복잡한 집합 연산을 효율적으로 처리할 수 있는 능력을 갖출 수 있게 될 것이다. 열심히 공부하자!
