[알고리즘] 비트마스크 알고리즘

비트마스트(BitMask)란?

비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료구조로 쓰는 기법을 말함
부분집합 생성,순열 및 조합 생성 등과 같은 문제 해결할때 쓰임

각 비트는 집합의 원소와 대응됨. 비트가 1이면 해당 원소가 집합에 존재. 0이면 존재X

장점
1. 수행시간이 빠름
비트연선이기때문에 O(1)에서 구현되는 것이 많음
2. 코드가 짧음
3. 메모리 사용량이 적음
ex> bit가 10개인 경우 각 bit당 두 가지 경우를 가지기 때문에 2^10가지의 경우를 10bit 이진수 하나로 표현이 가능

하나의 정수로 많은 경우의 수를 표현할 수 있어서 메모리 측면에서 효율적이며, 더 많으 메모리를 미리 계산해서 저장해 둘 수 있는 장점이 있음(DP에 유용)

https://gyoogle.dev/blog/algorithm/BitMask.html