[BOJ, Python] 비트마스크(BitMask) 정리 ( with 11723 - 집합 )

11723번: 집합

비트마스크는 특정 알고리즘이 아닌, 이진수와 비트 연산자를 활용한 효율적인 연산 테크닉이다. 백준의 11723번 집합 문제는 비트마스킹을 활용한 대표적인 문제로, 비트마스크 기법을 직접 설명하기보단 해당 문제의 예제를 하나씩 해결해보며 정리해본다.

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.
- add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
- remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
- check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
- toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.(1 ≤ x ≤ 20)
- all: S를 {1, 2, ..., 20} 으로 바꾼다.empty: S를 공집합으로 바꾼다.

<< (SHIFT) , | (OR)

# 집합 S 초기화
S = 0

# add n
S ^= 1 << n

비트연산자 <<, >>는 쉬프트 연산자이다. 1을 추가하는 해당 명령에서 n << 1은 10······00 (n의 위치에 1이 존재)을 반환한다.
0으로 초기화된 S와 OR 연산(|)을 실행하면 양쪽에 하나라도 포함되어 있을 때 1을 반환하기 때문에 해당 연산의 최종값은 10······00이 된다.

& (AND)

# check n
print(1 if S & (n << 1) != 0 else 0)

&은 AND 연산자이다. 양쪽 모두가 1을 가지고 있어야만 1을 반환한다. 따라서 집합 S에 n이 있는지 판단하기 위해 S와 (1 << n)의 AND 연산을 하여 0이 아닌지만 판단한다. (1 << n)은 n을 제외한 나머지가 모두 0이기에 나머지 자리에서는 0을 반환할 테고 n의 위치에서는 S의 n이 있어야 할 위치와의 판단만 이루어질 것이다.

~ (NOT)

# remove n
S &= ~(1 << n)

~는 NOT 연산자이다. 0은 1로, 1은 0으로 변환한다. n를 제외한 나머지 값은 그대로 유지될 테고, S와 n의 위치의 값에 상관 없이 0과 AND 연산을 진행하므로 무조건 0이 된다.

^ (XOR)

# toggle n
S ^= (1 << n)

^는 XOR 연산자이다. XOR 연산자는 두 비트가 서로 다를 때 1, 같을 때 0을 반환한다. 따라서 집합 S의 해당 위치가 1이면 0을, 0이면 1을 반환하게 된다.

초기화

# all
S = (1 << 21) - 1

# empty
S = 0

해당 문제에서 집합의 크기는 20이다. 21까지 쉬프트를 해주면 1000000000000000000000이 되고, 여기에 1을 빼주면 11111111111111111111을 반환하여 집합을 모두 채울 수 있다. 비우는 방법은 처음과 동일하다. 0으로 초기화시킨다.