[자료구조] 집합(set)

집합(Set)은 

 - 원소(Member)라는 구별되는 객체들이 연관되어 모인 것이다.

 - 서로 다른 연관된 원소들의 순서 없는 모임이다.

특징

- 순서가 없다.

- 원소들끼리 서로 다르다

응용

1. 그래프

 - 객체들 사이의 관계나 연결로 정의되는 문제(?)들을 모델링하는 데 전형적으로 사용되는 자료구조다.

 - 그래프를 표현하는 가장 일반적인 방법은 인접 리스트(adjacency list)를 사용하는 것이다.

 - 인접 리스트는 하나의 정점에 인접한 정점들을 갖는다.

 - 인접 리스트를 표현하는 한 방법은 인접한 정접들의 집합으로 표현하는 것이다.

2. 그래프 알고리즘

 - 그래프로 모델링되는 문제들을 푸는 알고리즘이다.

 - 흔히 그래프 알고리즘은 정점들이나 에지들을 함께 모으는 데 집합을 사용한다.

 - 예를들어, 최소 신장 트리(minimum spanning tree)를 구하는 Kruskal의 알고리즘은 커가는 최소 신장트리를 유지하기 위해 하나의 집합을 사용한다.

 - 트리에서 사이클을 피하기 위해서 정점들의 집합을 사용한다.

3. 관계대수

 - 데이터베이스 시스템의 이론적인 질의(query) 언어다. 근본적으로 집합 이론은 모든 질의 언어들의 기본을 형성한다.

 - 예를들어, 어떤 소프트웨어 회사의 문제 보고서 데이터베이스에서 SQL(Structured Query Language)을 사용해서 질의한다고 가정하자, 상태가 Open이거나(개발자가 그 문제를 처리하고 있음을 의미) Wait인(개발자가 아직 시작하지 않음을 의미) 문제들을 처리하는 모든 개발자을 위한 질의를 할 수 있다. 실제로 이 질의는 어떤 한 상태를 갖는 모든 레코드들의 합집합이다.

성질

 1. 멱등의 법칙(idempotency law)

 - S n S = S

 - S U S = S

 2. 드모르간의 법칙(Demorgan law)

 - 한 집합의 차집합을 다른 두 차집합의 교집합이나 합집합으로 표현할 수 있다.

 - S1 - (S2 U S3) = (S1 - S2) n (S1 - S3)

 - S1 - (S2 n S3) = (S1 - S2) U (S1 - S3)

인터페이스

...

1. set_insert : O(n) : 삽입되는 원소가 이미 존재하는지 확인 필요.

2. set_remove : O(n)

3. set_union : O(nm) : 두 집합의 원소 수의 곱

 - set1의 원소들에 대해 list_lns_next를 반복 호출해서 set1의 원소들을 setu에 넣는다.

 - set2의 원소들이 비슷한 방식으로 setu에 넣어지는데, setu에 같은 원소가 중복되지 않도록 삽입하기 전에 확인을한다.

4. set_intersection : O(nm)

5. set_difference : O(nm)

6. set_is_member : O(n)

7. set_is_subset : O(nm)

8. set_is_equal : O(nm)

집합 예제 : 집합 커버

 - 집합 커버(set covering)는 조합론과 자원 선택 등의 많은 문제를 잘 모델링하는 최적화 문제이다.

 - 집합 S와 S의 부분집합 A_1에서 A_n으로 이루어진 집합 P와 P의 부분집합 C에 대해 S의 모든 원소가 C의 원소들에 속하면 C는 S의 커버라고 한다.

 - 또, C는 가능한 한 적은 수의 집합으로 이루어져야 한다.

 - S가 팀에 필요한 기술집합이고, P는 각 선수들의 기술 집합의 집합이라고 하자. P에서 C에 넣어진 선수들의 기술은 S의 기술을 모두 만족시켜야 한다. 그리고 가능한 가장 적은 수의 선수를 선택해야 한다.