여러 개의 선택 상태를 비트로 압축해서 저장하는 동적 계획법이다.

보통 DP는 상태를 배열 인덱스로 표현하는데, 선택 여부가 여러 개 있을 때 그 상태를 하나하나 배열이나 리스트로 들고 다니면 너무 크고 느리다.

예시

• 1번 원소를 선택했는지
• 2번 원소를 선택했는지
• 3번 원소를 선택했는지
• …
• N번 원소를 선택했는지

이걸 [True, False, True, …]로 관리할 수 있지만 비트마스크는 정수 하나로 표현 가능

예시 : N=4일 때

• 0000 : 아무것도 선택 안함
• 0001 : 0번만 선택
• 0101 : 0번과 2번 색택
• 1111 : 전부 선택

왜 비트마스크를 쓰는가?

상태를 압축하기 위해서

예를 들어 원소가 N개 있을 때, 각 원소는 선택/비선택 2가지 상태를 가진다.

그러면 전체 상태 수는 : 2^N

즉 모든 부분집합을 표현할 수 있다.

이걸 리스트로 저장하는 것보다 정수 하나로 표현하면 훨씬 다루기 쉽다.