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

먼저 그림 7-17의 a 와 같이 s에서 1을 뺀 s – 1과 ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
a s 0 0 0 0 0 1 1 0 1 0 1 0
논리곱 연산을 하면 s에서 가장 아래쪽의 비트가 0
s - 1 0 0 0 0 0 1 1 0 1 0 0 1
으로 바뀝니다. 즉, 집합 {1, 3, 5, 6}에서 1이 삭제 &
0 0 0 0 0 1 1 0 1 0 0 0
됩니다.
집합 s에서 가장 아래쪽에 있는 1이 0으로
바뀝니다.

그런 다음 다시 s에 대해 같은 연산을 수행합니다 ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
b s 0 0 0 0 0 1 1 0 1 0 0 0
( b ). 여기서도 가장 아래쪽의 비트가 1에서 0으로
s - 1 0 0 0 0 0 1 1 0 0 1 1 1
바뀝니다. 즉, 집합 {3, 5, 6}에서 3이 삭제됩니다. &
0 0 0 0 0 1 1 0 0 0 0 0

집합 s에서 가장 아래쪽에 있는 1이 0으로
바뀝니다.
c 와 d 도 마찬가지의 과정을 거칩니다. 그러면 모

든 비트가 0이 됩니다. 이때 가장 아래쪽의 비트를 ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
c s 0 0 0 0 0 1 1 0 0 0 0 0
삭제하는 연산을 수행하면 집합의 원소가 1개씩 삭
s - 1 0 0 0 0 0 1 0 1 1 1 1 1
제되는데, 이 연산 횟수가 곧 집합의 원소 개수가 &
0 0 0 0 0 1 0 0 0 0 0 0
됩니다.
집합 s에서 가장 아래쪽에 있는 1이 0으로
바뀝니다.

３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
d s 0 0 0 0 0 1 0 0 0 0 0 0
s - 1 0 0 0 0 0 0 1 1 1 1 1 1
&
0 0 0 0 0 0 0 0 0 0 0 0
집합 s에서 가장 아래쪽에 있는 1이 0으로
바뀝니다.
모든 원소를 출력하는 Print / PrintLn 함수 [그림 7-17] 원소의 개수 세기

Print와 PrintLn 함수는 집합의 모든 원소를 출력하는 함수입니다. 예를 들어, 집합 s의 원소

가 {1, 5, 7}이면 { 1 5 7 }이라고 출력합니다.

비트 벡터로 집합을 표현하는 프로그램의 ‘집합 연산’을 위한 함수의 개수는 배열로 집합을 표현

하는 프로그램보다 ‘집합 연산’을 위한 함수의 개수가 적습니다. 배열로 집합을 표현하는 프로그
램보다 적은 개수의 함수로 다양한 연산을 수행할 수 있기 때문입니다. 여기서는 다음과 같이 선
언한 집합 s1, s2를 사용해 집합의 연산에 대해 생각해 보겠습니다. 먼저 집합 s1, s2를 준비합니다.

07•집합 297