📌 비트마스크(BitMask)

비트마스크(bitmask)는 하나의 정수 변수를 여러 상태(플래그) 저장이나 특정 연산의 효율적인 처리를 위해 ‘이진수 비트 단위’로 사용하기 위한 기법

📕 python에서의 비트 연산자

1. AND(&): 두 비트가 모두 1이면 결과가 1, 아니면 0
2. OR(|): 두 비트 중 하나라도 1이면 결과가 1, 둘 다 0이면 0
3. XOR(^): 두 비트가 서로 다르면 1, 같으면 0
4. NOT(~): 단항 연산자로 모든 비트를 반전
5. 왼쪽 시프트(<<): 비트를 왼쪽으로 이동 (2의 거듭제곱 곱과 유사)
6. 오른쪽 시프트(>>): 비트를 오른쪽으로 이동 (2의 거듭제곱 나눗셈과 유사)

a = 0b1010  # 10진수로 10
b = 0b1100  # 10진수로 12

print(bin(a & b))  # 0b1000  -> 8
print(bin(a | b))  # 0b1110  -> 14
print(bin(a ^ b))  # 0b0110  -> 6
print(bin(~a))     # 파이썬에서는 음수로 표현됨(보수 표기 주의)
print(bin(a << 1)) # 0b10100 -> 20
print(bin(a >> 1)) # 0b0101  -> 5

📕 비트마스크의 주요 활용

1. 플래그(Flag) 관리

   여러 개의 ON/OFF 상태를 한 번에 관리 가능

   	예: 한 사람이 4가지 자격증을 가지고 있다면, 각각의 자격증 보유 여부를 비트 하나씩으로 표현 가능.

2. 부분 집합(Subset) 생성 및 순회

   어떤 집합의 모든 부분 집합을 순회할 때, 인덱스에 해당하는 비트가 1이면 그 원소가 포함된 것으로 간주하는 방식.

   예: {1, 2, 3}의 모든 부분 집합을 비트마스크로 표현하면,
   0b000 = {}
   0b001 = {1}
   0b010 = {2}
   0b011 = {1,2}
   0b100 = {3}
   0b101 = {1,3}
   0b110 = {2,3}
   0b111 = {1,2,3}

3. 조합적 문제 해결

   예: n명의 사람 중 특정 속성을 가진 사람의 조합을 구하거나, 그래프 문제에서 방문 상태 등을 표현할 때 유용

   방문 여부를 “비트마스크”로 관리하면, 방문 기록을 O(1)에 체크할 수 있고, 백트래킹(DFS) 등의 알고리즘에서 빠른 상태 관리 가능

4. DP(Dynamic Programming)에서의 상태 표현

   예: 외판원 순회 문제(TSP)에서 어떤 도시들을 방문했는지 상태를 비트마스크로 표현하여 DP 테이블을 구성하는 기법 등.

🔖예시

부분 집합 순회 예시

arr = [10, 20, 30]
n = len(arr)

# 부분 집합 개수: 2^n
for subset_mask in range(1 << n):  # 0부터 2^n - 1까지
    subset = []
    for i in range(n):
        # i번째 비트가 켜져있으면, arr[i]를 부분 집합에 포함
        if subset_mask & (1 << i):
            subset.append(arr[i])
    print(f"mask={bin(subset_mask)} -> subset={subset}")

✒️ 예시문제

집합
IP 주소
소수 만들기