비트마스킹

집합의 상태를 정수의 각 비트로 표현하는 기법. 원소가 N개인 집합을 N비트 정수 하나로 나타낸다. (i번 비트가 1이면 i번 원소가 집합에 있음)

집합 연산이 비트 연산 한 번으로 끝나 빠르고, 무엇보다 상태를 정수 하나로 압축할 수 있어 DP의 상태로 쓰기 좋다.

기본 연산

• 원소 추가: state | (1 << i)
• 원소 제거: state & ~(1 << i)
• 원소 토글: state ^ (1 << i)
• i번 원소 포함 여부: state & (1 << i) (0이 아니면 포함)
• 전체 집합: (1 << n) - 1
• 켜진 비트 수: __builtin_popcount(state)

주의

• 1 << i에서 i가 크면(31 이상) 오버플로. long long이면 1LL << i로 써야 한다.
• 연산자 우선순위 때문에 state & (1 << i)처럼 괄호를 꼭 챙긴다.

부분집합 순회

어떤 집합 state의 모든 부분집합을 도는 관용구:

for (int sub = state; sub > 0; sub = (sub - 1) & state) {
    // sub: state의 부분집합
}

비트 DP

방문한 정점 집합, 사용한 원소 집합처럼 “어떤 것들을 골랐는가”를 상태로 삼는 DP. 외판원 순회(TSP) 가 대표적이다. dp[현재정점][방문집합] 꼴로 정의해, 상태 수 O(N · 2^N)에 푼다.

기본 코드 구조

int n = 5;
int state = 0;               // 빈 집합

state |= (1 << 2);           // 2번 원소 추가
state |= (1 << 4);           // 4번 원소 추가

if (state & (1 << 2)) {      // 2번 원소가 있는가?
    // 있음
}

state &= ~(1 << 2);          // 2번 원소 제거

int full = (1 << n) - 1;     // {0,1,2,3,4} 전체 집합