비트 마스킹 (Bit Masking)

JayJi·2026년 4월 4일

목록 보기

13/30

문제	난이도	핵심
11723번 — 집합	실버 V	비트 집합 구현
1094번 — 막대기	실버 III	비트 연산 활용
2098번 — 외판원 순회	골드 I	비트 DP
1285번 — 동전 뒤집기	골드 IV	비트 완전 탐색
9663번 — N-Queen	골드 IV	비트로 가지치기

1. 개념

비트 마스킹(Bit Masking)은 정수의 각 비트를 플래그(true/false)처럼 사용해 집합이나 상태를 표현하는 기법이다.

정수 하나로 N개의 ON/OFF 상태를 동시에 표현한다.

정수 13 = 0b 1 1 0 1
인덱스      3 2 1 0

→ 0번, 2번, 3번이 ON / 1번이 OFF인 상태

boolean[] 대신 int 하나로 상태를 표현하므로 메모리가 적고 연산이 빠르다.

2. 비트 연산자 정리

연산자	기호	의미	예시
AND	`&`	둘 다 1이면 1	`1010 & 1100 = 1000`
OR	`\\|`	하나라도 1이면 1	`1010 \\| 0101 = 1111`
XOR	`^`	다르면 1	`1010 ^ 1100 = 0110`
NOT	`~`	비트 반전	`~1010 = 0101`
왼쪽 시프트	`<<`	비트를 왼쪽으로 이동	`1 << 3 = 1000 (=8)`
오른쪽 시프트	`>>`	비트를 오른쪽으로 이동	`1000 >> 2 = 10 (=2)`

3. 핵심 포인트 2가지

집합 연산을 비트 연산으로 표현한다

집합 연산	비트 연산	의미
i 추가	`state \\|= (1 << i)`	i번 비트를 1로
i 제거	`state &= ~(1 << i)`	i번 비트를 0으로
i 포함 여부	`(state & (1 << i)) != 0`	i번 비트가 1인지
i 토글	`state ^= (1 << i)`	i번 비트 반전
전체 집합	`(1 << N) - 1`	N개 비트 모두 1
공집합	`0`	모든 비트 0

부분집합 순회와 방문 상태 압축에 쓴다

비트 마스킹의 핵심 활용 2가지다.

부분집합 열거: N개의 원소로 만들 수 있는 모든 부분집합을 0부터 (1<<N)-1까지 순회
방문 상태 압축: visited[] 배열 대신 int 하나로 방문 상태를 표현 → DP 테이블 크기 대폭 축소 (외판원 순회 등)

4. 코드

기본 비트 연산

int state = 0;          // 공집합: 0000

// i번 원소 추가 (OR)
state |= (1 << 2);      // 0000 → 0100 (2번 추가)
state |= (1 << 0);      // 0100 → 0101 (0번 추가)

// i번 원소 제거 (AND NOT)
state &= ~(1 << 2);     // 0101 → 0001 (2번 제거)

// i번 원소 포함 여부 확인 (AND)
boolean has0 = (state & (1 << 0)) != 0;  // → true
boolean has2 = (state & (1 << 2)) != 0;  // → false

// i번 원소 토글 (XOR)
state ^= (1 << 1);      // 0001 → 0011 (1번 토글)

// 전체 집합 (N=4)
int full = (1 << 4) - 1;  // → 1111 (=15)

// 원소 개수
int count = Integer.bitCount(state);  // 1인 비트 개수

모든 부분집합 순회

int N = 4;

for (int state = 0; state < (1 << N); state++) {
    System.out.print("{ ");
    for (int i = 0; i < N; i++) {
        if ((state & (1 << i)) != 0) {
            System.out.print(i + " ");
        }
    }
    System.out.println("}");
}
// { } → {0} → {1} → {0,1} → {2} → ... → {0,1,2,3}

특정 집합의 모든 부분집합 순회

// state의 모든 부분집합 순회 (공집합 제외)
for (int sub = state; sub > 0; sub = (sub - 1) & state) {
    // sub는 state의 부분집합
}

방문 상태 압축 DP (외판원 순회 기본 틀)

int N = 4;
int[][] dist = new int[N][N];       // 도시 간 거리
int[][] dp = new int[1 << N][N];    // dp[방문상태][현재도시]

// 방문 상태를 비트로 압축
// dp[visited][cur] = visited 상태에서 cur 도시에 있을 때 최솟값
for (int visited = 0; visited < (1 << N); visited++) {
    for (int cur = 0; cur < N; cur++) {
        if (dp[visited][cur] == 0) continue;

        for (int next = 0; next < N; next++) {
            if ((visited & (1 << next)) != 0) continue;  // 이미 방문

            int nextVisited = visited | (1 << next);
            dp[nextVisited][next] = Math.min(
                dp[nextVisited][next],
                dp[visited][cur] + dist[cur][next]
            );
        }
    }
}

5. 시간복잡도

연산	시간복잡도
단일 비트 연산 (추가/삭제/확인/토글)	O(1)
모든 부분집합 순회	O(2^N)
특정 집합의 부분집합 순회	O(2^K) — K는 1인 비트 수
비트 DP (외판원 순회)	O(N² × 2^N)

N이 20 이하일 때 2^N 순회가 가능하다. N이 커지면 지수적으로 늘어나므로 주의해야 한다.

6. 주의사항

int는 32비트, long은 64비트다. N이 32를 초과하면 int 대신 long을 사용하고 1L << i로 시프트해야 한다.
1 << 31은 음수가 된다. Java의 int는 부호 있는 32비트이므로 31번 비트가 부호 비트다. N이 30 이하일 때만 int로 안전하게 쓸 수 있다.
연산자 우선순위에 주의하라. state & (1 << i) != 0은 !=가 먼저 계산된다. 반드시 (state & (1 << i)) != 0으로 괄호를 명시하라.
Integer.bitCount(state)로 1인 비트 수를 O(1)에 구할 수 있다. 직접 루프 돌리지 않아도 된다.
비트 DP는 N ≤ 20 정도가 한계다. 2^20 = 1,048,576이므로 N이 커질수록 메모리와 시간이 급격히 늘어난다.