알고리즘 자료구조 - 8

7장

1)
집합(set)
 - 명확한 조건을 만족하는 자료의 모임
 - 객관적으로 범위를 규정한 어떠한 자료의 모임
 - 각 자료를 원소(element)라 한다


2)
부분집합: A 집합의 모든 원소가 B 집합의 원소에 포함될 경우, A는 B의 부분집합(subset)이다
진부분집합: A 집합의 모든 원소가 B 집합의 원소에 포함되고 A 집합과 B 집합이 같지 않을 경우, A는 B의 진부분집합(proper subset)이다

집합의 연산
 - 합집합: A 집합과 B 집합의 모든 원소를 합친 집합
 - 교집합: A 집합과 B 집합 양쪽 모두 속하는 원소의 집합
 - 차집합: A-B일 경우, A 집합의 원소 중 B 집합과 겹치는 원소를 제외한 집합

 

 

3)
배열로 집합 만들기
 - 배열을 사용하여 집합을 표현하려면 집합의 원소개수와 배열의 요소개수가 같아야한다
 
 - 배열에 대한 정보를 가지고 있는 구조체를 구성한다
    : 집합의 최대크기(==배열의 크기), 집합의 원소개수(==현재 배열의 저장된 요소 수), 배열을 가리키는 포인터
 - 함수
    : init, check, add, remove, size, assign, equal, union(합집합), intersection(교집합), difference(차집합), terminate

 

 

4)
비트 벡터로 집합 만들기
 - 비트 벡터(bit vector): 비트를 사용하여 정수 집합을 구성한 집합(즉 각 정수 원소를 하나의 비트로 표현한 집합)
 - 전체집합(universal set): 대상이 되는 모든 원소를 포함한 집합. 즉, unsigned 32비트 크기를 가지는 집합일 경우 전체집합은 0~31을 가진다

 - 함수: add, remove, size, union(합집합, |), intersection(교집합, &), difference(차집합, & ~)
   ** 함수를 구할시, bit set, bit clear를 사용하여 구현한다
   ** 비트 벡터는 정수값을 가지기 때문에 집합이 같은지 확인하는 방법은 등가연산자(==, !=)를 사용해도 된다