비트마스크 (Bitmask)
한눈에 보기
정수의 각 비트로 집합의 포함 여부를 표현하는 비트마스크 기법을 다룬다. 기본 비트 연산 정리, 부분집합 열거, 외판원 순회 동적 계획법 구현과 주의점을 정리한다.
최종 업데이트 2026.09.17
비트마스크(Bitmask)는 정수 하나의 각 비트를 켜고 끄면서 집합을 표현하는 기법이다. 원소가 20개인 집합을 배열이 아니라 정수 하나로 다룰 수 있고, 합집합·교집합 같은 연산이 비트 연산 한 번으로 끝난다.
코딩테스트에서는 두 가지 상황에서 쓴다. 하나는 모든 부분집합을 완전 탐색해야 할 때, 다른 하나는 "어떤 것들을 이미 방문했는가"를 DP 상태에 넣어야 할 때다. 원소 개수가 20 남짓으로 작게 제한되어 있으면 비트마스크를 의심해볼 만하다.
집합을 정수 하나로
규칙은 단순하다. i번째 비트가 1이면 원소 i가 집합에 있다는 뜻이다.
원소를 추가한다는 것
집합에 원소 5를 넣고 싶다면, 5번 비트만 켜진 값 1 << 5를 만들어 OR 연산을 하면 된다. OR는 둘 중 하나라도 1이면 1이므로, 기존 비트는 그대로 두고 5번만 켜진다.
외워야 할 관용구
| 하고 싶은 일 | 코드 | 설명 |
|---|---|---|
| 원소 i 추가 | mask | (1 << i) | OR로 해당 비트만 켠다 |
| 원소 i 제거 | mask & ~(1 << i) | 해당 비트만 0인 마스크와 AND |
| 원소 i 포함 여부 | mask & (1 << i) | 0이 아니면 포함 |
| 원소 i 토글 | mask ^ (1 << i) | XOR는 켜진 건 끄고 꺼진 건 켠다 |
| 전체 집합 (원소 n개) | (1 << n) - 1 | 비트 n개가 전부 1 |
| 공집합 | 0 | |
| 합집합 / 교집합 | a | b / a & b | |
| 차집합 (a에서 b 빼기) | a & ~b | |
| 켜진 비트 개수 | bin(mask).count('1') | 파이썬 3.10+는 mask.bit_count() |
| 가장 낮은 켜진 비트 | mask & -mask | 펜윅 트리에서도 쓰는 관용구 |
mask & (1 << i)는 포함일 때 1이 아니라 2i를 반환한다는 점에 주의한다. 참·거짓 판정에는 문제없지만, 1과 직접 비교하면 틀린다. 굳이 0/1로 만들고 싶으면 (mask >> i) & 1을 쓴다.
모든 부분집합 순회하기
원소가 n개면 부분집합은 2n개다. 0부터 2n−1까지 세기만 하면 모든 부분집합을 한 번씩 만든다. 이게 비트마스크를 쓰는 가장 큰 이유다.
items = ['A', 'B', 'C']
n = len(items)
for mask in range(1 << n): # 0 ~ 7, 총 8가지
subset = [items[i] for i in range(n) if mask & (1 << i)]
print(mask, subset)
# 0 []
# 1 ['A']
# 2 ['B']
# 3 ['A', 'B']
# 4 ['C']
# ...
# 7 ['A', 'B', 'C']
특정 집합의 부분집합만 돌고 싶을 때 쓰는 관용구도 있다. 겉보기엔 이상하지만 정확히 부분집합만, 중복 없이 훑는다.
sub = mask
while sub:
process(sub)
sub = (sub - 1) & mask # 다음으로 작은 부분집합으로 점프
process(0) # 공집합은 따로 처리
sub - 1은 가장 낮은 켜진 비트를 끄고 그 아래를 전부 켜는데, & mask로 원래 집합 밖의 비트를 지워버린다. 결과적으로 부분집합만 내림차순으로 나온다.
비트마스크 DP
"이미 방문한 도시들의 집합"처럼 순서는 상관없고 어떤 것들을 골랐는지만 중요한 상태는 비트마스크로 표현하기 좋다. 외판원 순회(TSP)가 대표적이다.
def tsp(dist, n):
"""dist[i][j] = i에서 j로 가는 비용. 0번에서 출발해 전부 돌고 돌아오는 최소 비용."""
INF = float('inf')
FULL = (1 << n) - 1
dp = [[INF] * n for _ in range(1 << n)] # dp[방문집합][현재위치]
dp[1][0] = 0 # 0번만 방문한 상태
for mask in range(1 << n):
for cur in range(n):
if dp[mask][cur] == INF:
continue
for nxt in range(n):
if mask & (1 << nxt): # 이미 방문했으면 건너뛴다
continue
nmask = mask | (1 << nxt)
cost = dp[mask][cur] + dist[cur][nxt]
if cost < dp[nmask][nxt]:
dp[nmask][nxt] = cost
return min(dp[FULL][i] + dist[i][0] for i in range(n))
상태 개수가 2n × n이라 n이 20을 넘으면 감당이 안 된다. 문제에서 "도시는 최대 16개" 같은 제약을 주면 비트마스크 DP를 쓰라는 신호로 읽으면 된다.
시간 복잡도
| 작업 | 복잡도 | 비고 |
|---|---|---|
| 원소 추가·제거·확인 | O(1) | 비트 연산 한 번 |
| 합집합·교집합·차집합 | O(1) | 배열이면 O(n) |
| 모든 부분집합 순회 | O(2ⁿ) | n ≤ 20 정도까지 현실적 |
| 부분집합의 부분집합 전부 | O(3ⁿ) | n ≤ 15 정도 |
| 비트마스크 DP (TSP) | O(2ⁿ × n²) | n ≤ 16 정도 |
자주 하는 실수
- 연산자 우선순위를 놓친다. 파이썬에서
&는==보다 우선순위가 낮다.mask & 1 << i == 0은 의도와 전혀 다르게 해석된다. 항상 괄호를 친다. mask & (1 << i) == 1로 비교한다. 결과는 2i지 1이 아니다.if mask & (1 << i):처럼 참·거짓으로 쓰거나(mask >> i) & 1을 쓴다.- 제거할 때
^를 쓴다. XOR는 토글이라 없는 원소에 쓰면 오히려 추가된다. 확실히 제거하려면& ~(1 << i)다. - 전체 집합을
1 << n으로 쓴다.(1 << n) - 1이어야 한다. 괄호를 빼면1 << (n - 1)로 읽히지도 않고 그냥 틀린 값이다. - n이 큰데 비트마스크를 쓴다. 230은 10억이다. n이 25만 넘어도 부분집합 순회는 불가능하다.
- 배열 인덱스와 비트 번호를 헷갈린다. 그림에서 보듯 이진수 표기는 왼쪽이 큰 비트인데 원소 번호는 오른쪽이 0번이다.
면접에서 이렇게 물어본다
- 비트마스크로 집합을 표현하는 원리를 설명해 보라.
- 원소 추가·제거·확인을 각각 어떤 연산으로 하는가.
- AND, OR, XOR가 집합 연산으로는 각각 무엇에 해당하는가.
- 모든 부분집합을 순회하는 코드를 써 보라.
- 비트마스크를 쓸 수 있는 n의 한계는 어느 정도이며 그 이유는 무엇인가.
- 비트마스크 DP가 적합한 문제의 특징은 무엇인가.
mask & -mask가 무엇을 반환하는지 설명해 보라.
알고리즘에서 같이 읽기
- 이분 탐색 (Binary Search)정렬된 배열에서 탐색 범위를 절반씩 줄여 O(log n)에 값을 찾는 이분 탐색의 원리와 동작 과정을 그림으로 정리했다. lower bound와 upper bound, 코딩테스트 단골인 파라메트릭 서치와 회전 정렬 배열, 구현 코드와 자주 하는 실수까지 다룬다.
- DFS와 BFS (Depth First Search, Breadth First Search)그래프의 모든 정점을 방문하는 DFS와 BFS의 원리와 방문 순서 차이를 스택과 큐로 설명하고, O(V + E) 복잡도, 구현 코드, 문제 유형별 선택 기준을 정리한다.
- 다익스트라 알고리즘 (Dijkstra's Algorithm)음수 간선이 없는 그래프에서 한 정점으로부터의 최단 거리를 구하는 다익스트라 알고리즘의 그리디 원리, 우선순위 큐 구현, 복잡도 비교와 한계를 정리한다.
- 동적 계획법 (Dynamic Programming)겹치는 부분 문제와 최적 부분 구조를 전제로 부분 문제의 답을 저장해 재사용하는 동적 계획법을 다룬다. 하향식과 상향식 비교, 문제 풀이 단계, 배낭 문제 구현을 정리한다.
이 개념, 내 코드에서는 어떻게 물어볼까요
데브핏(DevFit)에 채용공고 URL을 붙여 넣고 레포지토리를 연결하면, 내가 쓴 커밋에서 예상 질문과 어필 포인트를 만듭니다. 하루 10회까지 무료입니다. 합불 판정이나 지원자 랭킹은 만들지 않고, 최종 판단은 사람이 합니다.
공고 넣고 시작하기