비트마스킹은 코딩테스트에서 자주 보이지만, 처음 배우면 연산자만 잔뜩 나와서 어렵게 느껴지기 쉽습니다. AND, OR, XOR를 외워도 정작 문제에서 언제 써야 하는지는 여전히 모호한 경우가 많습니다.
이번 글에서는 비트마스킹을 연산자 트릭이 아니라, 여러 개의 on/off 상태를 정수 하나로 압축하는 상태 표현법으로 설명하겠습니다.
비트마스킹이 필요한 순간은 어떤 모습일까
비트마스킹은 보통 여러 개의 yes/no 상태를 한 번에 관리해야 할 때 자연스럽게 등장합니다. 예를 들어 어떤 원소를 포함했는지, 어떤 도시를 방문했는지, 어떤 스위치가 켜져 있는지처럼 각 항목이 둘 중 하나 상태만 가질 때 잘 맞습니다.
이런 문제를 배열이나 set으로도 표현할 수는 있습니다. 하지만 항목 수가 많지 않다면 정수 하나의 각 비트에 상태를 넣는 편이 훨씬 compact하고 빠르게 다룰 수 있습니다.
왜 집합처럼 볼 수 있을까
예를 들어 원소 4개가 있으면, 4비트 정수 하나로 이 집합을 표현할 수 있습니다. 0번 비트가 켜져 있으면 0번 원소 포함, 1번 비트가 켜져 있으면 1번 원소 포함, 이런 식입니다.
즉 정수 하나가 “어떤 원소들이 현재 선택되어 있는가”를 나타내는 집합처럼 동작합니다. 그래서 비트마스킹은 부분집합 탐색에서 특히 자주 등장합니다.
mask = 0
# 2번 원소 추가
mask |= (1 << 2)
# 2번 원소 포함 여부 확인
if mask & (1 << 2):
print("included")
# 2번 원소 제거
mask &= ~(1 << 2)
# 2번 원소 토글
mask ^= (1 << 2)입문자가 많이 헷갈리는 부분은 여기서 연산자 의미보다 “무슨 상태를 표현하고 있는가”를 놓친다는 점입니다. mask가 현재 선택된 원소 집합이라는 생각이 먼저 잡혀야, 각 연산도 자연스럽게 읽힙니다.
부분집합 문제에서 왜 자주 나오나
부분집합은 각 원소를 고를지 말지 두 가지 선택으로 이루어집니다. 즉 원소 n개면 2^n개의 상태가 생깁니다. 이 구조는 비트열과 정확히 잘 맞습니다.
그래서 부분집합을 하나씩 생성하거나, 특정 상태에서 다음 상태로 넘어가야 하는 문제는 비트마스크로 표현하면 훨씬 단단하게 정리됩니다. 방문한 도시 집합, 선택한 과목 조합, 켜진 스위치 상태 같은 문제들이 대표적입니다.
방문 상태를 배열 대신 마스크로 들고 다닌다는 뜻
예를 들어 어떤 DFS나 DP 문제에서 방문한 도시 집합을 visited 배열로 매번 따로 들고 다니기보다, mask 하나로 현재 방문 집합을 표현할 수 있습니다. 이게 바로 상태 압축(state compression)입니다.
상태 압축을 쓰면 메모리 표현이 compact해질 뿐 아니라, DP 테이블의 인덱스로도 바로 쓰기 좋아집니다. 그래서 비트마스킹은 단독 기법이라기보다 DP나 그래프 탐색의 상태 표현 도구로 자주 등장합니다.
문제에서 어떤 신호가 보이면 비트마스킹일까
- 원소 수가 작고, 각 원소는 선택/비선택 두 상태만 가진다
- 부분집합 전체를 돌거나 방문 상태를 같이 들고 다녀야 한다
- 토글, 켜기/끄기, 포함/제외가 핵심 동작이다
- 배열보다 더 압축된 상태 표현이 필요하다
이 신호가 보이면 연산자 암기보다 먼저 “아 이건 상태를 비트로 표현하면 되겠다”는 생각이 들어야 합니다.
헷갈리는 포인트
- 1 << k가 무엇을 뜻하는지보다, k번 상태를 가리키는 표시라는 점
- OR는 켜기, AND는 확인/부분 추출, XOR는 토글이라는 역할 차이
- mask가 단순 숫자가 아니라 현재 상태 집합이라는 점
- 비트마스킹이 언제 배열이나 set보다 더 자연스러운지 판단하는 기준
즉 비트마스킹은 비트 연산 자체가 중요한 것이 아니라, 상태를 표현하는 방식이 더 중요한 주제입니다. 이 순서를 거꾸로 배우면 계속 어렵게 느껴집니다.
마무리
비트마스킹의 핵심은 여러 개의 on/off 상태를 정수 하나에 압축해 넣는 사고법입니다.
즉 부분집합, 방문 상태, 토글 문제처럼 상태가 0/1로 갈릴 때 비트마스킹은 매우 강력한 표현 도구가 됩니다.
