경우의 수를 나타낼 수 있는 다양한 방법이 있다. 비트마스크는 원소를 선택하는 경우와 선택하지 않는 경우 둘로 나뉘는 문제에 유용하게 활용할 수 있는 방법이다.
1. 비트마스크
마스크는 두 값을 합쳐 and, or, nor등의 연산을 수행하는 것으로, 이를 비트 연산에 적용한 것이 비트마스트다. 비트는 컴퓨터 연산의 최소 단위이므로 연산 과정에 다른 변환이 불필요하기 때문에 매우 빠른 속도를 갖는다는 장점이 있다. 비트마스크를 적용할 수 있는 문제라면 수행 시간, 메모리 면에서 큰 이점이 있다.
2. 비트 연산자
and, or, xor, nor, nand 연산자는 두 개의 비트를 입력으로 받아 하나의 비트를 출력으로 내놓는다. 두 비트에 대해 각 연산자 별 출력은 다음과 같다.
| a | b | and | or | xor | nor | nand |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
그리고 비트 시프트 연산자는 <<, >>가 있다. <<는 비트를 왼쪽으로, >>는 오른쪽으로 밀어주는 연산자로 만약 1<<3이라는 비트 시프트 연산을 수행하면 1이라는 비트를 3칸 왼쪽으로 밀어 1000이 된다. 5<<2는 101을 오른쪽으로 2칸 밀어 10100이 된다.
비트 연산자를 활용한 두 값의 비트마스크를 수행하면 특정 상황에 원하는 값을 얻을 수 있다. 매우 빠르고 작은 메모리로. and를 활용하면 부분 집합을 얻을 수 있다.
3. 비트마스크로 부분집합 구하기
3개의 원소를 갖는 집합 A가 있다. A = {2, 5, 9}이다. 각 원소를 선택하거나, 선택하지 않거나 두 가지 경우가 있다. 따라서 모든 원소에 대해 2가지 경우의 수를 생각해 2×2×2 = 8 가지의 부분집합을 얻을 수 있다. 각 원소를 하나의 비트라고 생각해보면 선택하지 않는 경우는 0, 선택하는 경우는 1로 표현할 수 있다. 그리고 이것은 이진수로 표기가 가능하고 000~111까지의 이진수 안에 모든 경우가 들어있다. 따라서 n개의 원소를 갖는 집합의 부분집합은 0~2n-1을 각각 이진수로 나타내 전체집합에 비트마스크를 수행하면 된다.
4. 소스코드
A = list(map(int,input().split()))
n = len(A)
subset = []
for i in range(1<<n):
mask = []
for j in range(n):
if i & (1<<j):
mask.append(A[j])
subset.append(mask)
print(*subset)
# input: 1 2 3
# output: [] [1] [2] [1, 2] [3] [1, 3] [2, 3] [1, 2, 3]
