비트마스크란?
•
정수의 비트를 이용해 집합(상태, 방문, 선택 등)을 표현하는 테크닉
•
보통 1 << n으로 **n개의 원소에 대한 2ⁿ가지 조합(부분집합)**을 만들 수 있음
부분집합 생성 (템플릿)
const n = nums.length;
for (let i = 0; i < (1 << n); i++) {
const subset = [];
for (let j = 0; j < n; j++) {
if (i & (1 << j)) {
subset.push(nums[j]);
}
}
console.log(subset);
}
TypeScript
복사
•
i: 0부터 2ⁿ - 1까지의 모든 비트패턴
•
i & (1 << j): i에서 j번째 비트가 1이면 해당 요소 포함
시간복잡도
•
i는 0 ~ 2ⁿ - 1 → 2ⁿ번 반복
•
j는 0 ~ n - 1 → 각 i마다 n번 반복
→ 총 O(n × 2ⁿ)
모든 부분집합을 1개씩 순회하면서 내부 요소 합산(XOR) → 전형적인 완전탐색 구조 방문 처리 예시
let visited = 0;
// 2번 노드 방문
visited |= (1 << 2);
// 2번 방문했는지 확인
if (visited & (1 << 2)) { ... }
// 2번 방문 해제
visited &= ~(1 << 2);
TypeScript
복사
응용 예시: XOR이 K 이상인 부분집합 개수 구하기
function countXorGreaterThanK(nums: number[], k: number): number {
const n = nums.length;
let count = 0;
for (let i = 1; i < (1 << n); i++) {
let xor = 0;
for (let j = 0; j < n; j++) {
if (i & (1 << j)) xor ^= nums[j];
}
if (xor >= k) count++;
}
return count;
}
TypeScript
복사
핵심 패턴 요약
연산 | 의미 |
1 << j | j번째 비트가 1인 마스크 |
i & (1 << j) | i에서 j번째 비트가 1인지 확인 |
`visited | = (1 << j)` |
visited &= ~(1 << j) | j번째 비트를 끄기 |
visited ^ (1 << j) | j번째 비트를 토글 |