집합과 상호배타적 집합의 개념
개념 : 집합은 순서와 중복이 없는 원소들을 갖는 자료구조. A라는 그룹의 원소 구성이 {1, 6, 6, 6, 4, 3} 이라면, 이는 집합으로 생각할 때 중복을 제외해 {1, 6, 4, 3}으로 생각해야 한다. 순서를 따지지 않는다.
집합의 종류
- 유한 집합 : 원소의 개수가 유한함.
- 무한 집합 : 원소의 개수가 무한함.
- 공집합 : 집합이 비어 있음.
- 상호배타적 집합 : 교집합이 없는 집합관계
상호배타적 집합이란 ?
교집합이 없는 집합 관계.
A = {1, 2, 3}
B = {4, 5, 6, 7}
이 두 집합의 원소 중 겹치는 원소가 없으면 교집합이 없다고 할 수 있고 이를 상호배타적 집합이라고 함.
상호배타적 집합의 특성을 활용하는 분야
코딩 테스트에서 항호배타적 집합을 배워야 하는 가장 현실적인 이유는 그래프 알고리즘에서 많이 활용하기 때문. 그래프 알고리즘에서는 흔히 사이클을 확인하는 일이 많아, 그 작업에 상호배타적 집합 개념을 활용한다.
- 이미지 분할 : 이미지를 서로 다른 부분으로 나누는 데 사용한다. 사람과 배경을 겹치지 않게 분할하는 데 사용될 수 있음.
- 도로 네트워크 구성 : 도로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는 데 사용할 수 있다.
- 최소 신장 트리 알고리즘 구현 : 최소 신장 트리 알고리즘의 구현에서 간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용한다.
- 개임 개발 : 캐릭터의 동작을 자연스럽게 구현할 수 있다. 예를 들어 플레이어와 적군이 충돌할 때 이 두 캐릭터가 겹치지 않도록 하는 데 사용할 수 있다.
- 클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성할 수 있다. 이렇게 작업간의 의존 관계가 없으면 동시에 여러 작업을 진행할 수 있다.
집합의 연산
보통 집합은 트리로 표현하며 대표적인 연산은 합치기와 탐색이 있다.
배열을 활용한 트리로 집합 표현하기
집합은 배열을 활용한 트리로 구현한다. 각 집합에는 대표 원소가 있어야 하므로 대표 원소에 대해 알아본다.
대표 원소란 ?
대표 원소는 집합의 원소 중 집합을 대표하는 역할을 한다.
배열로 집합을 표현하는 것이란 ?
집합을 배열로 표현한다는 것은 하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다는 것을 의미한다. 그리고 집합을 트리 형태로 표현할 때는
- 배열의 인덱스는 자신을 배열 값은 부모 노드를 의미한다.
루트 노드는 부모 노드가 없고, 자기 자신이 부모 노드이다. 다시 말해 루트 노드는 값 자체가 배열의 인덱스와 동일하다
배열의 크기에 대해서 배열의 인덱스가 모든 집합의 원소를 표현할 수 있으면 된다.
유니온-파인드 알고리즘 (Union & Find Algorithms)
집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다. 합치기는 유니온(Union), 탐색을 파인드(Find), 이들을 묶어서 유니온-파인드 알고리즘이라고 한다.
파인드 연산
파인드 연산은 특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다. 보통 파인드 연산은 특정 노드가 같은 집합에 있는 확인할 때 사용한다. 예를 들어, A, B 노드가 있는데 이 노드의 루트 노드가 서로 같다면 같은 집합에 속한다고 할 수 있다. 특정 노드부터 재귀로 거슬러 올라가며 루트 노드를 찾았던 과정이다.
- 현재 노드의 부모 노드를 확인한다. 부모 노드를 확인하다가 부모 노드가 루트 노드이면 탐색을 종료한다.
- 1. 에서 탐색이 종료되지 않으면 1. 을 반복한다.
찾기 연산을 설명하는 데 사용할 집합을 정의하고, 노드 7의 루트 노드를 찾는 과정을 find(7)로 표현하였다.
노드 7의 루트노드를 찾는 과정을 위 과정대로 진행하였다. 노드 7 의 부모 노드는 6이며, 현재 노드와 부모 노드가 같지 않기 때문에 현재 노드를 부모 노드인 6으로 변경합니다. 이를 반복하여 부모 노드가 1이고, 현재 노드가 1이 되었을 때 탐색을 종료하고 루트 노드 1을 찾았다.
합치기 연산
합치기 연산은 두 집합을 하나로 합치는 연산이다. '두 집합을 합친다'는 것은 두 집합의 루트 노드를 같게 하는 것이다. 이때 루트 노드는 두 집합의 루트 노드 중 하나가 되면 된다.
- 두 집합에서 찾기 연산을 통해 루트 노드를 찾는다.
- 찾은 두 루트 노드의 값을 비교
- 두 집합을 합친다. 두 집합의 루트 노드를 같게 한다. 이때 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관 없다.
- 집합 A = {1, 3, 5}, 집합 B = {2, 7, 9} 두 집합이 있다.
- 집합 A와 B의 말단 노드 중 임의의 노드 5와 7의 루트 노드를 찾는다고 한다면, 찾기 연산을 수행하여 노드 5가 속한 집합의 루트 노드는 1, 노드 7의 루트 노드는 2이다.
- 루트 노드가 2인 집합의 루트 노드를 1로 바꾼다. 이렇게 하면 2의 루트 노드가 1이 되면서 자연스럽게 두 집합을 합칠 수 있게 된다.
- 집합 A는 변경된 것이 없으나 집합 B는 루트 노드의 부모노드가 2에서 1로 바뀌었다. 9에서 부모 노드를 쫓아가면 1이 나온다.
합치기 연산의 연산 비용 문제 해결 -> 랭크
랭크란 ?
랭크란 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말한다.
랭크 기반으로 합치기 연산하는 방법에 대해 알아보도록 하자.
- 두 노드의 루트 노드를 구한다.
- 1에서 구한 루트 노드의 랭크를 비교
- 랭크 값이 다르면 랭크 값이 큰 루트 노드를 기준으로 삼는다. 즉, 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꾼다. 이때 트리의 깊이는 더 깊어지지 않으므로 랭크의 값은 변하지 않는다.
- 랭크 값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더한다.
문제 33. 간단한 유니온-파인드 알고리즘 구현하기
def union(parents, x, y) :
# 두 개의 집합을 합치는 함수
root1 = find(parents, x) # x가 속한 집합의 루트 노드 찾기
root2 = find(parents, y) # y가 속한 집합의 루트 노드 찾기
parents[root2] = root1 # y가 속한 집합을 x가 속한 집합에 합침
def find(parents, x) :
# 루트 노드 찾는 함수
if parents[x] == x : # 만약 x의 부모가 자기 자신이면, 즉 x가 루트 노드라면
return x
# 그렇지 않다면 x의 부모를 찾아서 parents[x]에 저장하고,
# 그 부모 노드의 루트 노드를 찾아서 parents[x]에 저장합니다.
parents[x] = find(parents, parents[x])
return parents[x] # parents[x]를 반환합니다
def solution(k, operations) :
parents = list(range(k)) # 처음에는 각 노드가 자기 자신을 부모로 가지도록 초기화
n = k # 집합의 개수를 저장할 변수, 처음에는 모든 노드가 서로 다른 집합에 있으므로 k
for op in operations : # operations 리스트에 있는 연산들을 하나씩 처리
if op[0] == 'u' : # 'u' 연산이면
union(parents, op[1], op[2]) # op[1]과 op[2]가 속한 집합을 합칩니다.
elif op[0] == 'f' : # 'f' 연산이면
find(parents, op[1]) # op[1]이 속한 집합의 루트 노드를 찾습니다.
# 모든 노드의 루트 노드를 찾아서 집합의 개수를 계산
n = len(set(find(parents, i) for i in range(k)))
return n