일지
알고리즘...100
niamdank
2022. 1. 10. 14:45
연결 리스트를 이용한 집합 처리
집합을 표현하기 위해 각 노드는 대표 노드(집합의 최초 노드)를 가리키는 포인터와, 다음 원소를 가리키는 포인터, 값을 나타내는 변수를 가진다.
또, 집합의 연산을 쉽게 하기 위해 각 노드는 tail 노드를 가리키는 포인터를 따로 가지고 있게 된다.
이 집합을 사용하기 위해서는 다음의 함수가 필요하다.
- MakeSet(x) 원소 x로 이루어진 집합을 만든다.
- FindSet(x) 원소 x를 가지는 집합을 찾는다.
- Union(x, y) 원소 x를 가진 집합과 원소 y를 가지는 집합을 하나로 합친다.
수행 시간은 MakeSet과 FindSet은 상수 시간이 걸리지만 Union은 집합의 크기에 따라 상수 시간을 벗어날 수 있다.
이 수행 시간을 최소화하기 위해 큰 집합에 작은 집합을 연결하는 방식을 사용한다.
※ Union 시 연결되는 집합은 대표 노드를 가리키는 포인터를 수정해 줘야 하므로 길이가 작은 게 유리하다.