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

07-3 비트 벡터로 집합 만들기

여기서는 비트 벡터로 배열을 구현하는 방법을 알아보겠습니다.

비트 벡터로 집합 만들기

집합의 최대 요소의 개수인 max의 값이 작을 경우 집합을 하나의 정수로 표현할 수 있습니
다. 그림 7-11과 같이 unsigned long형이 32비트라고 가정합니다. 이때 정수를 구성하는 비

트의 나열을 비트 벡터(bit vector)라고 하겠습니다.

위쪽 비트 아래쪽 비트
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
B 31 B 30 B 29 B 28 B 27 B 26 B 25 B 24 B 23 B 22 B 21 B 20 B 19 B 18 B 17 B 16 B 15 B 14 B 13 B 12 B 11 B 10 B 9 B 8 B 7 B 6 B 5 B 4 B 3 B 2 B 1 B 0
[그림 7-11] unsigned long형으로 표현한 비트 벡터

그림처럼 아래쪽 비트부터 시작해 각 비트를 B0, B1, B2, ..., B31이라고 부르겠습니다. 비트
벡터 안의 값은 각 원소의 유무에 따라 1, 0을 대입합니다. 예를 들어 집합에 x가 들어 있으면
Bx에 1을, 들어 있지 않으면 Bx에 0을 대입합니다. 그러면 32비트의 부호가 없는 정수 하나
로 {0, 1, ..., 31}을 전체집합(universal set)으로 표현할 수 있습니다.

전체집합은 대상이 되는 모든 원소를 포함한 집합입니다. 비트 벡터로 표현할 수 있는 집합은 전체집합인 {0, 1, ..., 31}
의 부분집합으로 제한됩니다.

예를 들어 원소가 하나도 없는 공집합 ∅는 그림 7-12의 a 처럼 표현합니다. 또 집합 {1, 5,
7, 17, 23}은 b 처럼 표현합니다.

a 공집합
３１ ３０ ２９ ２８ ２７ ２６ ２５ ２４ ２３ ２２ ２１ ２０ １９ １８ １７ １６ １５ １４ １３ １２ １１ １０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

b 집합{1, 5, 7, 17, 23}
３１ ３０ ２９ ２８ ２７ ２６ ２５ ２４ ２３ ２２ ２１ ２０ １９ １８ １７ １６ １５ １４ １３ １２ １１ １０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0

[그림 7-12] 비트 벡터로 집합을 표현한 예

07•집합 291