집합을 숫자 하나로! 비트마스킹

• 비트로 집합을 표현한다.
• 원소를 넣고 빼고 확인한다 (| & ^).
• 2ⁿ 개의 부분집합을 훑는다.
• 같은 순회로 XOR·OR 조건을 센다.
• 비트 DP 의 맛을 본다.

비유로 이해하기 — 전등 스위치 줄

스위치 20개가 줄지어 있다냥. 켜진 스위치가 "그 원소가 집합에 있다" 라냥. 스위치 전체의 상태를 숫자 하나로 적어두는 게 비트마스크라냥.

{1, 3} 은 1번과 3번 스위치만 켜진 것 → 2진수 101 → 숫자 5 라냥.

전체와 비움도 간단하다냥.

• 1~20 을 모두 켜기: mask = (1 << 20) - 1
• 통째로 비우기: mask = 0

오늘 1번 문제가 이 여섯 연산이라냥. 집합 자료구조 없이 정수 하나로 다 된다냥.

1 << (x - 1) 은 "x번 자리만 켠 비트" 라냥. x 가 1이면 맨 오른쪽, x 가 20이면 스무 번째 자리라냥. 전체·비움 연산에서는 x 를 쓰지 않으니 비트를 계산하지 말자냥. (x 가 0으로 들어와서 1 << -1 이 되면 에러라냥.)

11장에서 본 그 부분집합이라냥

11장에서는 "각 원소를 고르거나 안 고르거나" 를 재귀로 뻗었다냥. 그게 바로 각 비트를 1로 하거나 0으로 하는 것과 똑같다냥.

재귀 대신 mask 를 0 부터 세면, 재귀 없이 모든 경우가 나온다냥. 코드가 훨씬 짧아진다냥.

크기가 1 이상인 부분집합만 셀 땐 1 부터라냥.

mask = 0 은 아무것도 안 고른 빈 부분집합이라냥. 빈 집합을 빼려면 range(1, 1 << n) 으로 1 부터 돌면 된다냥.

오늘 2번 문제(XOR)에서 빈 집합을 실수로 세면 틀린다냥. 특히 목표가 0 일 때, 빈 집합의 XOR 도 0 이라 하나가 더 세진다냥.

n 이 커지면 2ⁿ 도 폭발한다냥. n 이 16이면 6만 5천쯤이라 괜찮지만, 30이 넘으면 못 쓴다냥. 그래서 이 방식은 n 이 작을 때 쓰는 무기라냥. 오늘 2·3번은 n 이 16까지라 안전하다냥.

왜 마스크가 상태가 되냥?

13장 DP 에서 상태는 보통 숫자 하나(dp[i])였다냥. 그런데 "어떤 것들을 골랐나" 같은 집합이 상태여야 하는 문제가 있다냥. 그때 마스크가 상태가 된다냥.

2ⁿ개의 상태라, 이것도 n 이 작을 때만 쓴다냥. 오늘 5번은 n 이 15까지라, 상태가 3만 개쯤이라 충분하다냥. 4번(집합 커버)도 같은 아이디어라냥.