비트마스크 (BitMask)

비트마스크는 정수 하나의 2진수 자리(비트)들을 스위치처럼 써서, 집합의 요소들이 들어 있는지 여부를 표현하는 테크닉입니다.

한눈에 보기

벽에 전등 스위치 5개가 한 줄로 붙어 있다고 생각해 보세요. 켜짐은 1, 꺼짐은 0입니다. "1번, 2번, 5번 켜짐"을 10011처럼 한 줄로 적을 수 있고, 이 한 줄은 곧 하나의 숫자입니다. 비트마스크는 이렇게 여러 개의 예/아니오를 정수 하나에 담는 방법입니다.

왜 비트마스크를 사용하나요?

DP나 순열 등, 배열만으로는 상태를 표현하기 번거롭거나 너무 무거운 문제를 풀 수 있음
작은 메모리와 빠른 수행시간으로 해결이 가능 (단, 원소의 수가 많지 않아야 함)
집합을 배열의 인덱스로 표현할 수 있음
코드가 간결해짐

원소 수가 n이면 가능한 부분집합이 2^n개라서, 보통 n이 20 안팎일 때까지 씁니다. (2^20은 약 100만, 2^30은 약 10억)

비트(Bit)란?

컴퓨터에서 사용되는 데이터의 최소 단위(0과 1)입니다. 2진법을 생각하면 편합니다.

우리가 흔히 쓰는 10진수를 2진수로 바꾸면?

9(10진수) → 1001(2진수)

자리	8	4	2	1
9의 2진수	1	0	0	1

8 + 1 = 9입니다. 오른쪽 끝 자리를 0번째 비트라고 부르고, 왼쪽으로 갈수록 1번째, 2번째, ... 비트입니다.

비트마스킹 활용해 보기

0과 1로 flag(깃발, 표시)를 활용해 보겠습니다.

[1, 2, 3, 4, 5]라는 집합이 있다고 가정해 봅시다. 여기서 임의로 몇 개를 골라 뽑아 확인해야 하는 상황이 주어졌습니다. (즉, 부분집합을 의미)

text

{1}, {2}, ..., {1,2}, ..., {1,2,5}, ..., {1,2,3,4,5}

물론 간단히 for문을 돌려 가며 배열에 저장해서 경우의 수를 구할 수도 있습니다. 하지만 비트마스킹을 하면 각 요소를 인덱스처럼 표현해 효율적으로 접근할 수 있습니다.

부분집합	2진수	10진수
[1, 2, 3, 4, 5]	11111	31
[2, 3, 4, 5]	11110	30
[1, 2, 5]	10011	19
[2]	00010	2

집합의 i번째 요소가 존재하면 1, 그렇지 않으면 0을 의미합니다. 이 표에서는 오른쪽 끝(0번째 비트)이 원소 1, 그 왼쪽이 원소 2, ... 맨 왼쪽(4번째 비트)이 원소 5입니다.

이런 2진수는 다시 10진수로 바꿀 수 있습니다. 11111은 10진수로 31이므로, 부분집합을 정수로 나타내는 것이 가능합니다. 31은 [1, 2, 3, 4, 5] 전체에 해당하는 부분집합이라는 뜻입니다.

이로써 부분집합에 i를 추가하고 싶을 때 해당 비트만 1로 바꿔 주면 표현할 수 있게 되었습니다. 이런 일은 비트 연산으로 제어합니다.

비트 연산

AND, OR, XOR, NOT, SHIFT가 있습니다. 아래 예시는 A = 1100, B = 1010입니다.

연산	기호	규칙	예시
AND	`&`	대응하는 두 비트가 모두 1일 때 1	`1100 & 1010 = 1000`
OR	`\|`	대응하는 두 비트 중 하나라도 1이면 1 (둘 다 1이어도 1)	`1100 \| 1010 = 1110`
XOR	`^`	대응하는 두 비트가 서로 다를 때 1	`1100 ^ 1010 = 0110`
NOT	`~`	비트 값을 반전	`~1100 = 0011` (4자리 기준)
SHIFT	`<<`, `>>`	왼쪽 혹은 오른쪽으로 비트를 옮김	`0001 << 2 = 0100`

왼쪽 시프트: A << B = A * 2^B
오른쪽 시프트: A >> B = A / 2^B (소수점 아래는 버림, 즉 A // 2^B. 예: 13 >> 1 = 6)

방향	비트 변화	10진수 변화
왼쪽	0001 → 0010 → 0100 → 1000	1 → 2 → 4 → 8
오른쪽	1000 → 0100 → 0010 → 0001	8 → 4 → 2 → 1

Python에서 ~는 조심해야 합니다. Python 정수는 자리 수 제한이 없어서 ~a가 -a - 1(음수)이 됩니다. 원하는 n자리만 남기려면 ~a & ((1 << n) - 1)처럼 n자리가 모두 1인 수와 AND 합니다.

비트 연산 연습문제: 백준 12813 (아래 Python 코드 참고)

동작 과정

연습이 되었다면, 다시 비트마스크로 돌아와 비트 연산을 활용해 봅시다. 크게 삽입, 삭제, 조회로 나뉩니다. (비트 번호는 오른쪽 끝이 0번째)

작업	식	예시 (i = 3)	결과
삽입	`S \| (1 << i)`	`10101 \| 01000`	`11101`
삭제	`S & ~(1 << i)`	`11101 & 10111`	`10101`
조회	`S & (1 << i)`	`10101 & 01000`	`0` (꺼져 있음)

1. 삽입

현재 10101로 표현되고 있을 때, i번째 비트 값을 1로 바꾸려고 합니다. i = 3이면 바꾼 뒤 11101이 나와야 합니다. 이때는 OR 연산을 활용합니다.

text

10101 | (1 << 3)

1 << 3은 1000이므로 10101 | 01000이 되어 11101을 만들 수 있습니다. OR는 이미 1인 자리는 그대로 두고, 3번째 자리만 1로 켭니다.

2. 삭제

반대로 0으로 바꾸려면 AND 연산과 NOT 연산을 활용합니다.

text

11101 & ~(1 << 3)

~(1 << 3)은 1000을 뒤집은 10111이므로, 11101 & 10111이 되어 10101을 만들 수 있습니다. 3번째 자리만 0이고 나머지는 1인 수와 AND 하니, 3번째 비트만 꺼집니다.

괄호가 꼭 필요합니다. ~가 <<보다 먼저 계산되기 때문에, ~1 << 3이라고 쓰면 (~1) << 3, 즉 ...11110000이 되어 아래 3개 비트까지 모두 지워집니다. (11101 & ~1 << 3의 결과는 10101이 아니라 10000)

3. 조회

i번째 비트가 무슨 값인지 알려면 AND 연산을 활용합니다.

text

10101 & (1 << i)

3번째 비트 값 : 10101 & (1 << 3) = 10101 & 01000 → 0
4번째 비트 값 : 10101 & (1 << 4) = 10101 & 10000 → 10000

이처럼 결과가 0이면 i번째 비트 값이 0인 것을 알 수 있습니다. (반대로 0이 아니면 무조건 1인 것)

이런 방법을 활용해 문제를 해결하는 것이 비트마스크입니다.

Python 코드

비트 연산 연습 (백준 12813)

길이가 같은 두 2진수 문자열 A, B를 받아 A & B, A | B, A ^ B, ~A, ~B를 차례로 출력하는 문제입니다.

python

def bit_ops(a_str, b_str):
    n = len(a_str)
    a = int(a_str, 2)                  # 1. '0'/'1' 문자열을 정수로
    b = int(b_str, 2)
    mask = (1 << n) - 1                # 2. n자리가 모두 1인 수 (NOT 결과를 n자리로 자르는 용도)
    results = [
        a & b,                         # 3. AND
        a | b,                         #    OR
        a ^ b,                         #    XOR
        ~a & mask,                     # 4. NOT A (mask로 n자리만 남김)
        ~b & mask,                     #    NOT B
    ]
    return [format(x, f'0{n}b') for x in results]  # 5. 다시 n자리 2진 문자열로


for line in bit_ops('0001100110', '1100110011'):
    print(line)
# 출력:
# 0000100010
# 1101110111
# 1101010101
# 1110011001
# 0011001100

int(문자열, 2)는 2진수 문자열을 정수로 바꿉니다.
n = 10이면 mask는 1111111111입니다.
AND, OR, XOR는 정수끼리 한 번에 계산됩니다. (원문 C 코드는 문자 한 글자씩 반복문으로 계산했는데, '0'과 '1'의 문자 코드가 마지막 비트만 다르다는 점을 이용한 것입니다.)
Python의 ~는 음수를 만들므로 mask와 AND 해서 n자리만 남깁니다.
format(x, '010b')처럼 쓰면 앞자리 0을 채워 n자리 2진 문자열로 돌려줍니다.

삽입, 삭제, 조회와 부분집합 돌기

python

items = [1, 2, 3, 4, 5]

# 1. 부분집합 <-> 정수: 원소 k는 오른쪽에서 (k-1)번째 비트
def to_mask(subset):
    mask = 0
    for x in subset:
        mask |= 1 << (x - 1)
    return mask

def to_subset(mask):
    return [items[i] for i in range(len(items)) if mask & (1 << i)]

print(format(to_mask([1, 2, 5]), '05b'), to_mask([1, 2, 5]))  # 출력: 10011 19
print(to_subset(0b11110))                                     # 출력: [2, 3, 4, 5]

# 2. 삽입: i번째 비트를 1로 (OR)
s = 0b10101
s = s | (1 << 3)
print(format(s, '05b'))            # 출력: 11101

# 3. 삭제: i번째 비트를 0으로 (AND + NOT), 괄호 필수
s = s & ~(1 << 3)
print(format(s, '05b'))            # 출력: 10101

# 4. 조회: i번째 비트가 켜져 있나 (AND)
print(s & (1 << 3))                # 출력: 0   -> 3번째 비트는 0
print(format(s & (1 << 4), '05b')) # 출력: 10000 -> 0이 아니므로 4번째 비트는 1

# 5. 모든 부분집합 돌기: 0 ~ 2^n - 1
n = 3
for mask in range(1 << n):
    print(format(mask, '03b'), to_subset(mask))
# 출력:
# 000 []
# 001 [1]
# 010 [2]
# 011 [1, 2]
# 100 [3]
# 101 [1, 3]
# 110 [2, 3]
# 111 [1, 2, 3]

원소 1은 0번째 비트, 원소 5는 4번째 비트에 대응시킵니다. 앞의 표와 같은 규칙입니다.
OR로 3번째 비트를 켭니다. 10101 → 11101.
~(1 << 3)과 AND 해서 3번째 비트만 끕니다. 11101 → 10101.
결과가 0이면 꺼짐, 0이 아니면 켜짐입니다.
0부터 2^n - 1까지의 정수가 곧 n개 원소의 모든 부분집합입니다. for문 하나로 부분집합 전체를 돌 수 있습니다.

시간복잡도와 공간복잡도

작업	최선	평균	최악	추가 공간
삽입 / 삭제 / 조회 (비트 1개)	O(1)	O(1)	O(1)	O(1)
모든 부분집합 나열	O(n · 2^n)	O(n · 2^n)	O(n · 2^n)	O(1) (나열용 정수 하나)
외판원 순회 비트마스크 DP	O(n^2 · 2^n)	O(n^2 · 2^n)	O(n^2 · 2^n)	O(n · 2^n)

비트 하나를 다루는 연산은 정수 하나에 대한 계산이라 O(1)입니다. (원소 수가 컴퓨터 정수 크기인 64 이하일 때 기준. Python은 더 큰 정수도 되지만 자리 수에 비례해 느려집니다.)
부분집합은 2^n개이고, 각각 원소 n개를 확인하므로 O(n · 2^n)입니다.
표기법은 시간 복잡도 글을 참고하세요.

활용 예: 외판원 순회 (백준 2098)

비트마스크 연습문제: 백준 2098

모든 도시를 한 번씩만 방문하고 다시 시작점으로 돌아오는 최소 비용을 구하는 문제입니다.

완전탐색으로도 답은 구할 수 있지만, N이 최대 16이라 방문 순서가 16!(출발 도시를 고정해도 15!, 약 1.3조)가지나 되어 시간 초과에 빠집니다.

따라서 DP를 활용해야 하고, "지금까지 어느 도시들을 방문했는지"를 배열로 관리하기 힘드므로 비트마스크를 활용하면 좋은 문제입니다. 방문한 도시 집합을 정수 하나(mask)로 나타내면, 그 정수를 DP 표의 칸 번호로 바로 쓸 수 있습니다. 이렇게 하면 계산량이 약 16 × 16 × 2^16 ≈ 1,700만으로 줄어듭니다.

dp[mask][cur] = "방문한 도시 집합이 mask이고 지금 cur 도시에 있을 때, 여기까지 오는 최소 비용"

python

INF = float('inf')


def tsp(w):
    n = len(w)
    full = (1 << n) - 1                # 1. 모든 도시를 방문한 상태 (n자리 모두 1)
    # 2. dp[mask][cur] = 방문한 도시 집합이 mask이고 지금 cur에 있을 때까지의 최소 비용
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0                       # 0번 도시에서 출발 (mask = 0001)

    for mask in range(1 << n):
        for cur in range(n):
            if dp[mask][cur] == INF:
                continue
            for nxt in range(n):
                # 3. 이미 방문했거나 길이 없으면 건너뜀 (조회)
                if mask & (1 << nxt) or w[cur][nxt] == 0:
                    continue
                new_mask = mask | (1 << nxt)   # 4. nxt 방문 표시 (삽입)
                cost = dp[mask][cur] + w[cur][nxt]
                if cost < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = cost

    # 5. 모두 방문한 뒤 0번 도시로 돌아오는 비용까지 더해 최솟값
    return min(dp[full][cur] + w[cur][0]
               for cur in range(n) if w[cur][0] != 0 and dp[full][cur] != INF)


w = [
    [0, 10, 15, 20],
    [5, 0, 9, 10],
    [6, 13, 0, 12],
    [8, 8, 9, 0],
]
print(tsp(w))  # 출력: 35

도시가 4개면 full은 1111(15)입니다.
칸의 개수는 (가능한 방문 집합 2^n) × (현재 도시 n)입니다. 처음엔 0번 도시만 방문한 상태(0001)에서 비용 0으로 시작합니다. 순회는 원을 그리므로 어느 도시에서 출발해도 답이 같습니다.
조회로 nxt가 이미 방문한 도시인지 확인합니다. w[cur][nxt] == 0은 길이 없다는 뜻입니다.
삽입으로 nxt를 방문 집합에 넣은 새 상태를 만들고, 더 싼 비용이면 갱신합니다. new_mask는 항상 mask보다 크므로, mask를 작은 수부터 돌면 필요한 값이 이미 채워져 있습니다.
모든 도시를 방문한 상태에서 출발점으로 돌아가는 길을 더해 가장 싼 값을 고릅니다. (순회가 가능한 입력만 주어진다고 가정)

예시의 답 35는 0 → 1 → 3 → 2 → 0 순서(10 + 10 + 9 + 6)입니다.

정리

개념	비전공자 버전 요약
비트마스크	스위치 여러 개의 켜짐/꺼짐을 숫자 하나에 담기
부분집합 ↔ 정수	들어 있는 원소 자리는 1, 없는 자리는 0
삽입	OR로 그 자리 스위치 켜기: `S \| (1 << i)`
삭제	NOT한 값과 AND로 그 자리만 끄기: `S & ~(1 << i)` (괄호 필수)
조회	AND 결과가 0이면 꺼짐, 아니면 켜짐: `S & (1 << i)`
비트마스크 DP	"어디를 방문했나"를 정수로 만들어 DP 표의 칸 번호로 쓰기

참고: mygumi 블로그 - 비트마스크, 백준 12813, 백준 2098

변수와 자료형

흐름 제어

함수

클래스와 객체

CLI와 파일 입출력

비트마스크 (BitMask)

한눈에 보기

왜 비트마스크를 사용하나요?

비트(Bit)란?

비트마스킹 활용해 보기

비트 연산

동작 과정

1. 삽입

2. 삭제

3. 조회

Python 코드

비트 연산 연습 (백준 12813)

삽입, 삭제, 조회와 부분집합 돌기

시간복잡도와 공간복잡도

활용 예: 외판원 순회 (백준 2098)

정리

비트마스크 (BitMask) ​

한눈에 보기 ​

왜 비트마스크를 사용하나요? ​

비트(Bit)란? ​

비트마스킹 활용해 보기 ​

비트 연산 ​

동작 과정 ​

1. 삽입 ​

2. 삭제 ​

3. 조회 ​

Python 코드 ​

비트 연산 연습 (백준 12813) ​

삽입, 삭제, 조회와 부분집합 돌기 ​

시간복잡도와 공간복잡도 ​

활용 예: 외판원 순회 (백준 2098) ​

정리 ​

비트마스크 (BitMask)

한눈에 보기

왜 비트마스크를 사용하나요?

비트(Bit)란?

비트마스킹 활용해 보기

비트 연산

동작 과정

1. 삽입

2. 삭제

3. 조회

Python 코드

비트 연산 연습 (백준 12813)

삽입, 삭제, 조회와 부분집합 돌기

시간복잡도와 공간복잡도

활용 예: 외판원 순회 (백준 2098)

정리