알고리즘...100

연결 리스트를 이용한 집합 처리

집합을 표현하기 위해 각 노드는 대표 노드(집합의 최초 노드)를 가리키는 포인터와, 다음 원소를 가리키는 포인터, 값을 나타내는 변수를 가진다.

 

또, 집합의 연산을 쉽게 하기 위해 각 노드는 tail 노드를 가리키는 포인터를 따로 가지고 있게 된다.

 

이 집합을 사용하기 위해서는 다음의 함수가 필요하다.

• MakeSet(x) 원소 x로 이루어진 집합을 만든다.
• FindSet(x) 원소 x를 가지는 집합을 찾는다.
• Union(x, y) 원소 x를 가진 집합과 원소 y를 가지는 집합을 하나로 합친다.

 

수행 시간은 MakeSet과 FindSet은 상수 시간이 걸리지만 Union은 집합의 크기에 따라 상수 시간을 벗어날 수 있다.

이 수행 시간을 최소화하기 위해 큰 집합에 작은 집합을 연결하는 방식을 사용한다.

 

※ Union 시 연결되는 집합은 대표 노드를 가리키는 포인터를 수정해 줘야 하므로 길이가 작은 게 유리하다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘