Page 298 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

BitSet s1, s2;

집합 s1과 s2가 같은지 확인하는 방법

두 집합 s1과 s2가 같은지 확인하려면 등가 연산자 ==, !=를 사용하면 됩니다. 이렇게 할 수
있는 이유는 두 집합이 같을 경우 정수 값이 같기 때문입니다.

s1 == s2 /* 집합 s1과 s2가 서로 같은지 확인 */
s1 != s2 /* 집합 s1과 s2가 서로 다른지 확인 */

교집합을 구하는 방법

두 집합 s1과 s2의 교집합은 비트 단위의 논리곱 연산자 &를 사용하면 구할 수 있습니다.

s1 & s2 /* 집합 s1과 집합 s2의 교집합 */

a 집합 {1, 3, 5, 6}과 {1, 3, 4}의 교집합을 구합니다. b 집합 {1, 3, 5, 6}과 {2, 4, 7}의 교집합을 구합니다.
３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０ ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
s1 0 0 0 0 0 1 1 0 1 0 1 0 s1 0 0 0 0 0 1 1 0 1 0 1 0
s2 0 0 0 0 0 0 0 1 1 0 1 0 s2 0 0 0 0 1 0 0 1 0 1 0 0
& &
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
교집합 {1, 3}을 얻었습니다. 교집합의 결과로 공집합(0)을 얻었습니다.
[그림 7-18] 두 집합의 교집합을 구하는 과정

합집합을 구하는 방법

집합 s1과 s2의 합집합은 비트 단위의 논리합 연산자 |로 구할 수 있습니다.

s1 | s2 /* 집합 s1과 집합 s2의 합집합 */

a 집합 {1, 3, 5, 6}과 {1, 3, 4}의 합집합을 구합니다. b 집합 {1, 3, 5, 6}과 {2, 4, 7}의 합집합을 구합니다.
３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０ ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
s1 0 0 0 0 0 1 1 0 1 0 1 0 s1 0 0 0 0 0 1 1 0 1 0 1 0
s2 0 0 0 0 0 0 0 1 1 0 1 0 s2 0 0 0 0 1 0 0 1 0 1 0 0
| |
0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0
합집합 {1, 3, 4, 5, 6}을 얻었습니다. 합집합 {1, 2, 3, 4, 5, 6, 7}을 얻었습니다.
[그림 7-19] 두 집합의 합집합을 구하는 과정

298 C 알고리즘