1. 서로소..?
- 중학교 수학시간에 ‘서로소’ 라는 개념을 들어본 적이 있는가?
- 영어로 (disjoint). 즉, 교집합이 없는 서로 다른 두 집합을 서로소 라고 부른다.
- 그렇다면, 지금 배우고 있는 python으로 서로소 (이하 ‘상호배타집합’ ) 을 어떻게 구할 수 있을까?
2. idea
0. 상호배타집합에 필수적인 연산
- Make-Set(x) : x가 자신을 가리키도록 초기화 하는 것.
- Find-Set(x) : x의 대표 요소가 있으면, 대표 요소를 가리키도록 타고 올라 가는 것
- Union(x,y) : x,y를 하나의 집합으로 합친다 ⇒ 즉, x,y 집합중에 대표자를 새로 정하는 것.
1. 연결리스트
- 먼저 단순하게 ‘연결리스트’로 표현해 볼 수 있을 것이다.
2. 트리
- 다음으로는 트리가 있다. 리스트 배열을 사용하여, 자식 index에 부모 노드 값을 갱신해서 사용할 수 있다.
| index | 1 | 2 | 3 | 4 |
| 1 | 1 | 1 | 3 |
1) 대표자를 찾는 함수, find_set()
def find_set(x): # 최종 대표자를 찾을 때까지 재귀를 타고 올라가는 함수
if p[x] != x:
return(find_set(p[x])
return x
p = [0, 1, 2, 1, 3, 5]
find_set(4) # output = 1- 위 방법을 사용하면, 부모를 타고 올라갈 때까지 계속 검색해야 하기 때문에, 연결된 자식들이 많고 복잡해질수록 시간이 걸린다는 단점이 있다. 따라서 이것을 보완하기 위한 해결책이
1) rank 사용, 2) p를 갱신시키는 압축경로(path compression)
rank의 사용은 union 하는 과정에서 다시 다뤄보기로 하고, 압축경로를 소개해 보도록 하겠다.
def find_set(x):
if p[x] != x:
p[x] = findset(p[x])
return p[x]
p = [0, 1, 2, 1, 3, 5]
find_set(4) # output = 1 - 얼핏보면 결과는 같아 보이나, print(p) 를 해보면 그 결과가 다름을 알 수 있다.
p = [0, 1, 2, 1, 1, 5]로 부모테이블에 부모 노드값이 갱신 된 것을 확인할 수 있다.
2) 합하는 함수, union(x,y)
def union(x,y):
# 내가 만드는 함수는, x의 대표값으로 합해보려고 한다.
p[find_set(y)] = find_set(x)- 얼핏 보기에는 문제가 없어 보인다. 하지만 아래처럼 이미 자식이 생긴 노드에 또 다른 노드가 생긴다면? 약간 머리가 아파오기 시작한다.
- 이 때 등장하는 개념이, 아까 말한 ‘rank’ 이다. rank 를 통해서 rank 가 높은 것을 기준으로 union을 하게 된다면! 이 문제를 깔끔하게 해결할 수 있다.
def union2(x,y):
x = find_set(x)
y = find_set(y)
if x == y:
return
if rank[y] > rank[x]:
x, y = y, x
# 랭크가 더 큰 집합에 속하도록 처리
p[y] = x
if rank[x] == rank[y]:
rank[x] += 1
Uploaded by N2T