비트마스킹(Bitmasking)

정의

• 비트마스킹이란,
  정수의 이진수(0/1) 표현을 활용해
  집합, 방문 여부, 상태 등을 압축적으로 표현하고
  빠르게 연산하는 테크닉

• 특히 DP(동적계획법), 집합 처리, 외판원 문제(TSP), 그래프 탐색 등
  “여러 가지 조합” 을 처리할 때 매우 유용

기본 원리

• 각 비트(0/1)가 특정 항목(도시, 원소, 상태 등)의 포함/미포함을 의미
• 32비트/64비트 정수는
  • 최대 32개/64개의 원소 집합을 하나의 숫자로 표현 가능
• 예)
  | 비트마스크 | 집합 의미 |
  |:———:|:——————–:|
  | 0b0000 | 아무것도 포함X |
  | 0b0101 | 0번, 2번 포함 |
  | 0b1111 | 0~3번 모두 포함 |
  | 0b1001 | 0번, 3번만 포함 |

자주 쓰는 연산자

실전 패턴 & 자주 쓰는 코드

1. 특정 원소 k가 포함됐는지 확인

```python if visited & (1 « k): # k번 원소/도시가 포함(방문)됨