비트마스킹(Bitmasking)

비트마스킹(Bitmasking)

"비트를 활용하여 여러 개의 상태를 효율적으로 저장하고 조작하는 기법"

• 정수의 이진수 표현을 이용하여 데이터를 압축적으로 저장
• 특정 비트를 켜거나(1), 끄거나(0), 토글(반전)하는 연산을 수행
• 집합 연산, 최적화 문제, DP, 그래프 탐색에서 자주 사용됨

---

비트마스킹 기본 개념

1. 비트(0과 1)를 사용하여 여러 개의 상태를 한 개의 정수로 표현
2. 각 비트가 특정 상태(ON/OFF)를 나타냄
3. 비트 연산자(&, |, ^, <<, >>)를 활용하여 빠르게 연산 가능

출처: https://rebro.kr/63

# 집합 구현
S = 0  # 빈 집합

# 원소 추가
S |= (1 << 2)  # {2} 추가
S |= (1 << 4)  # {2, 4} 추가

# 원소 존재 확인
print(bool(S & (1 << 2)))  # True (2 있음)
print(bool(S & (1 << 3)))  # False (3 없음)

# 원소 제거
S &= ~(1 << 2)  # {4} 남음
print(bin(S))  # 0b10000


# 부분 집합_n개의 원소로 만들 수 있는 모든 부분 집합 구하기
arr = [1, 2, 3]
n = len(arr)

for bitmask in range(1 << n):  # 2ⁿ 개의 부분 집합
    subset = [arr[i] for i in range(n) if bitmask & (1 << i)]
    print(subset)


# DP에서 상태 저장_비트마스킹을 사용하여 방문한 노드 상태를 저장
# visited = 0b101 (노드 0, 2 방문)
visited = (1 << 0) | (1 << 2)

# 특정 노드(1) 방문 여부 확인
if visited & (1 << 1):
    print("노드 1 방문함")
else:
    print("노드 1 방문 안 함")

# 노드 1 방문 처리
visited |= (1 << 1)
print(bin(visited))  # 0b111 (노드 0, 1, 2 방문)

---

비트 연산 기초

연산	연산자	설명
AND	&	두 비트가 모두 1이면 1, 아니면 0
OR	`	`
XOR	^	다르면 1, 같으면 0
NOT	~	0은 1로, 1은 0으로 변환
왼쪽 시프트	<<	비트를 왼쪽으로 이동 (2배 증가)
오른쪽 시프트	>>	비트를 오른쪽으로 이동 (2배 감소)

---

비트마스킹의 시간복잡도

 

• 비트 연산(AND, OR, XOR 등)은 O(1)
• 집합 연산을 비트마스킹으로 구현하면 O(1)로 가능
• 부분 집합 생성은 O(2ⁿ) (브루트포스 방식)
• 비트 연산은 O(1)이므로 매우 빠르게 동작 가능

---

비트마스킹의 장단점

장점

 

• 메모리 절약 (정수 하나로 여러 상태 저장 가능)
• 빠른 연산 (O(1) 시간복잡도)
• 집합 연산, DP 최적화, 그래프 탐색에 유용

단점

 

• 비트 연산을 이해해야 사용 가능
• 비트 개수가 많아지면 해석이 어려움
• 부분 집합 탐색은 O(2ⁿ)으로 지수 시간이 걸릴 수 있음

결론

비트마스킹(Bitmasking)은 정수의 비트를 활용하여 상태를 저장하고 조작하는 기법으로, 집합 연산, DP, 그래프 탐색에서 매우 유용하게 사용됩니다. 특히, 빠른 연산과 메모리 절약이 필요한 문제에서 강력한 도구가 될 수 있습니다.