비트마스킹

비트마스킹이란

작은 원소 집합(보통 \(n \le 20\))을 정수 하나의 이진 비트로 표현하는
기법입니다. \(i\)번째 비트가 1이면 "원소 \(i\)를 포함", 0이면 "미포함"입니다.
집합 연산을 비트 연산으로 바꾸면 매우 빠르고, 상태 압축 DP의 토대가 됩니다.

예를 들어 \(\{0, 2, 3\}\)은 이진수 \(1101_2 = 13\)입니다.

핵심 연산 사전

1 << i를 쓸 때 \(i \ge 31\)이면 int가 넘칩니다. 이때는 1LL << i로 써야
합니다 — 가장 흔한 함정입니다.

모든 부분집합을 순회

크기 \(n\)인 집합의 모든 부분집합은 \(0\)부터 \(2^n - 1\)까지의 정수에 대응합니다.

for (int mask = 0; mask < (1 << n); mask++) {
    // mask가 하나의 부분집합
}

원소 \(i\)가 켜져 있는지 보며 부분집합의 내용을 읽습니다. 전체 순회는 \(O(2^n)\).

어떤 부분집합의 "부분집합들"만 순회

mask의 부분집합만 효율적으로 도는 유명한 관용구가 있습니다.

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

모든 mask에 대해 이 루프를 합치면 전체 비용이

$$ \sum_{mask} 2^{\text{popcount}(mask)} = 3^n $$

이 됩니다. 각 원소가 "양쪽에 없음 / 큰 집합에만 / 양쪽에"의 세 가지 상태를
갖기 때문입니다. 부분집합 DP의 단골 복잡도가 \(O(3^n)\)인 이유입니다.

복잡도 감각

\(2^{20} \approx 10^6\), \(3^{20} \approx 3.5 \times 10^9\) 정도이니, \(n\)이
20을 넘으면 비트마스킹은 보통 무리입니다. 다음 강의에서 구현 디테일과 응용을
봅니다.

켜진 비트 다루기

개수 세기 (popcount)

int c1 = __builtin_popcount(mask);    // int
int c2 = __builtin_popcountll(mask);  // long long

c = bin(mask).count('1')   # 또는 mask.bit_count()  (3.10+)

가장 낮은 켜진 비트

int low = mask & (-mask);   // 최하위 1비트만 남긴다
mask &= mask - 1;           // 최하위 1비트를 끈다

mask & -mask는 음수의 2의 보수 표현 덕분에 가장 낮은 켜진 비트를 정확히
집어냅니다. 켜진 비트만 골라 도는 빠른 순회에 자주 씁니다.

for (int m = mask; m; m &= m - 1) {
    int i = __builtin_ctz(m);   // 가장 낮은 켜진 비트의 위치
    // 원소 i 처리
}

파이썬에서의 주의

파이썬 정수는 임의 정밀도라 오버플로는 없지만, 비트 연산 우선순위가 낮아
괄호가 필수입니다.

if mask & (1 << i):       # 괄호 없으면 (mask & 1) << i 로 해석된다
    ...
mask |= (1 << i)          # 원소 추가
mask &= ~(1 << i)         # 원소 제거

응용 1 — 작은 집합 완전 탐색

원소 \(n \le 20\)개를 "선택/미선택"으로 전부 시도할 때, 중첩 반복문 대신
\(2^n\) 마스크 순회로 깔끔하게 짭니다.

int best = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) sum += a[i];
    if (sum <= limit) best = max(best, sum);
}

응용 2 — 상태 압축 DP의 토대

"방문한 정점 집합", "사용한 칸 집합" 등을 마스크로 들고 전이하면 외판원
문제(TSP)나 격자 도미노 채우기 같은 문제를 풉니다. 이는 다음 단원
비트마스크 DP 로 이어집니다.

응용 3 — 빠른 집합 연산

여러 집합의 합집합/교집합/포함 검사를 정수 연산으로 처리하면 상수배가 매우
작습니다. 예: \(n \le 60\)짜리 인접 관계를 long long 마스크로 두고 클릭
탐색을 가속.

흔한 함정 정리

• 1 << i 오버플로 — \(i \ge 31\)이면 1LL << i. 가장 자주 틀리는 부분입니다.
• 부호 비트 — int의 31번째 비트는 부호라 음수가 됩니다. 큰 마스크는
  unsigned나 long long을 쓰세요.
• 연산 우선순위 — mask & 1 << i는 mask & (1 << i)가 아닙니다. 항상
  괄호로 명확히.
• popcount 타입 불일치 — long long 마스크엔 __builtin_popcountll.

비트마스킹은 그 자체로 한 가지 알고리즘이라기보다, 작은 집합을 다루는 강력한
표현 도구 입니다. 이 도구가 손에 익으면 완전 탐색과 상태 DP가 훨씬 짧고
빨라집니다.

출제 신호

비트마스킹은 단독 출제보다 "작은 집합을 상태로 들고 다녀야 할 때"의 도구로
나옵니다. 이런 신호를 보면 손이 먼저 비트로 가야 합니다.

• \(N \le 20\) — 가장 강력한 신호. \(2^{20} \approx 10^6\)이라 전체 부분집합 열거가 됩니다.
• "모든 부분집합에 대해", "원소를 골라서", "각 사람이 좋아하는 메뉴의 집합"
• 상태가 "지금까지 방문한/사용한 원소들의 집합"으로 요약되는 문제
  (이 경우는 비트마스크 DP 단원으로 넘어갑니다)
• 알파벳 26종, 요일 7종처럼 원소 종류가 고정된 소집합의 포함 여부 관리

\(N \le 40\)이면 반으로 쪼개는 중간에서 만나기(meet in the middle)까지 의심합니다.

풀이 결정 절차

1. 집합의 크기가 비트로 들 수 있는 범위(\(\le 20{\sim}25\)비트)인지 확인합니다.
2. 필요한 연산을 비트 연산으로 번역해 봅니다 — 포함 s & (1 << i),
   추가 s | (1 << i), 제거 s & ~(1 << i), 토글 s ^ (1 << i).
3. 전체 열거가 필요한가? \(2^N\)개 마스크 순회 \(\times\) 마스크당 작업량으로
   복잡도를 검산합니다. \(2^{20} \times 20 = 2 \times 10^7\) 정도면 충분히 빠릅니다.
4. "어떤 마스크의 부분집합만" 돌아야 하면 아래의 부분집합 순회 관용구를 씁니다.

// m의 모든 부분집합 (공집합 제외) — 전체 합계 O(3^N)
for (int s = m; s; s = (s - 1) & m) {
    // s 는 m 의 부분집합
}

이 관용구는 공집합에서 멈추므로, 공집합도 필요하면 루프 뒤에 따로 처리합니다.

자주 하는 실수

• 32비트 시프트 오버플로 — 1 << n에서 \(n \ge 31\)이면 C++에선 미정의 동작입니다.

long long bad  = 1 << 40;     // 오버플로 (int 시프트)
long long good = 1LL << 40;   // 반드시 1LL

• 연산자 우선순위 — &는 ==보다 낮습니다. 괄호 없이 쓰면 의도가 뒤집힙니다.

if (s & (1 << i))        // 올바름
if (s & 1 << i == 0)     // (1<<i)==0 이 먼저 평가됨 — 버그

• 포함 검사 결과를 1과 비교 — (s & (1 << i)) == 1은 \(i \ne 0\)이면 항상 거짓입니다.
  0인지 아닌지로만 판정하세요.
• 파이썬에서의 착각 — 파이썬 정수는 자릿수 제한이 없어 시프트 오버플로는 없지만,
  bin(s).count('1') 반복 호출은 느립니다. 3.8+면 s.bit_count()
  (3.10 미만은 bin(s).count('1')를 미리 테이블화)로 대체합니다.

연습 방법

사이드바의 연습 문제를 쉬운 것부터 푸세요. 첫 단계는 "집합 자료구조를
정수 하나로 바꿔치기"만 하는 문제(예: 좋아하는 메뉴 조합 세기)로 비트 연산
번역을 손에 익히고, 다음 단계에서 부분집합 순회 관용구가 필요한 문제로
넘어가면 됩니다. 풀 때마다 &, |, ^, ~, << 다섯 연산을 주석 없이도 읽을 수
있는지 점검하세요. 태그된 문제를 3문제 이상 해결하면 알고리즘이 마스터
처리되어 레이팅 CLASS 보너스에 들어갑니다.