[자료구조] 비트 마스크

1. 비트마스크

- 직렬화된 단위요소들로 데이터의 특성을 표시한 자료 구조

피자를 예로 들면, 1~20번가지의 토핑가지수가 있을 때 20비트로 표현할 수 있음 (1 ->  토핑 들어감, 0 -> 토핑 X)

 

- 집합을 표현해낼 때 좋은 자료 구조

부분 집합 개념을 실행할 수 가 있어서, 고구마 무스 피자에 들어간 토핑 수가 N가지라고 할 때 2^N에 대하여 비트 연산으로 빠르게 순회가 가능함

 

2. 무엇을 할 수 있나

- 집한간 비교시, 유의미한 요소를 뽑아낼 수 있을 것

• 합( | 연산자) = 두 피자에 들어간 토핑은?
• 교( & 연산자) = 두 피자에 공통적으로 들어간 토핑은?
• 차( &와 - 연산자 이용) = A 피자에만 특별히 들어간 토핑은?

 

- 집합 내 가능한 조합의 경우의 수를 구하는 문제에서 활용 가능할 것

[부분집합 개수 공식] 출처.https://mathbang.net/286

 

3. 참고

https://github.com/snrndi121/algorithm_baekjoon/tree/master/etc/bitmask

snrndi121/algorithm_baekjoon