오늘은 분리집합에 대해 araboza.
알고 배울 땐 서로소집합이라 배워서, 처음 분리집합이라는 말 듣고 뭔가 했는데 같은 거였다.
일단 알고보면 뭔가 알고문제 풀 때 쓸 일도 많고,
특히, MST만들 때, 보통 크루스칼 알고리즘을 쓰다보니까 익숙해진 감도있다.
분리집합
서로 교집합 없이 분리되어 있는 집합으로 표현하는 일종의 자료구조
역시 글보단 시각적인게 뭔가 좋으니까
간단히 1번부터 6번 노드까지 있다고 가정하자.
각각은 각각이 하나의 집합을 이루고 있다고 생각하면 총 6개의 집합이 있는 셈이다.
각 집합의 대표는 자기 자신을 가리키고 있다.
reps = list(range(7))
# [0, 1, 2, 3, 4, 5, 6]0번 인덱스를 제외하고 초기상태의 각 인덱스가 자기 자신을 가리킨다고 생각하면 된다.
이제 여기서 2번 노드가 1번 노드와 하나의 집합을 이룬다고 생각하자.
그러면 2번 노드는 1번 노드를 가리키고, 총 5개의 집합이 된다.
reps = [0, 1, 1, 3, 4, 5, 6]마찬가지로 4번과 5번 노드는 3번 노드를 가리킨다고 생각하면,
reps = [0, 1, 1, 3, 3, 3, 6]이 되겠지?
아무튼 이러한 연산을 하는데 필요한 두 가지 함수가 있다.
- 각 집합의 대표노드(자기 자신을 가리키는 노드)를 찾는 함수
- 집합을 합치는 함수
일반적으로는, find, union 함수라고 부른다.
구현하는 방법이야 사람마다 다르겠지만, 나는
# 각 집합의 대표노드를 찾는 함수
def find(n):
if reps[n] != n:
reps[n] = find(reps[n])
return reps[n]
# 두 개의 집합을 합치는 함수
def union(node1, node2):
rep1 = find(node1)
rep2 = find(node2)
reps[rep2] = rep1이렇게 쓰는 편이다.
많은 사람들 코드를 보면,
def find(n):
if reps[n] != n:
return find(reps[n])
return n이런식으로 구현하거나,
union 함수에서 트리의 수준에 따라 대표노드를 무엇으로할지 결정하는 과정도 거치던데,
애초에 find함수에서 대표노드를 계속 갱신해주면 트리 수준은 계속 1로 갱신되니까
어디에 무엇을 결합하든 큰 의미는 없다고 느껴진다.
그리고 find 함수에서 대표노드를 갱신해주지 않으면 비효율성이 생기기도 한다.
대표적으로 다음같은 경우,
find 함수로 6번 노드의 대표노드를 찾으려면 총 5번 재귀가 일어난다.
그리고 또 다시 6번 노드의 대표노드를 찾으로고하면 또 5번번 재귀가 일어난다.
대표노드는 1로 항상 고정되어 있고,
추후에 탐색할 때의 비효율성을 없애기 위해,
이런 구조를
계속 이렇게 낮은 트리 수준으로 갱신해줄 필요가 있다.
아무튼 그래서 find 함수를
def find(n):
if reps[n] != n:
reps[n] = find(reps[n])
return reps[n]이렇게 쓴다고 난..
MST도 그렇고 지금까지 접했던 문제들도 그렇고
분리집합 문제들은 뭔가 이후에 그리디한 문제풀이와 많이 연결되는 거 같다.
근데 뭔가 보다보면, 분리집합으로 해결할 수 있을 거 같지만
시간초과 나는 문제들도 많다.
아무래도 집합을 트리처럼 접하다보니까 그래프탐색처럼 접근하는게 더 빠를 때가 많다.
이런거..,
사실 분리집합만 보면 그렇게 어려운 문제들이 많지는 않은데..
이제 분리집합처럼 트리를 형성하는데 각 간선 사이에 가중치가 있거나하면
조금씩 난이도가 높아진다.
ex. 3830...
아직 많이 어려운 문제는 못 풀어보기도 했고..,
아직 알고 공부 많이 못 해서 다른 알고리즘하고 결합된 문제에 접근성이 떨어지다보니
공부 더 열심히 해야겠다는 생각 뿐..,
끝!
