[자료구조] 비트마스크(BitMask) 알고리즘

비트마스크는 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 

이진수 즉, 0과 1만을 이용하므로 하나의 비트는 참/거짓을 의미한다. 

 

시간 복잡도(수행시간)가 O(1)이라는 엄청난 장점이 있다.

공간 복잡도(메모리 사용량) 또한 적다. bit가 10개라면 2^10까지의 표현이 가능한 것이다. 

그래서 DP같은 다이나믹 프로그래밍에 매우 적절하다.

 

논리회로 등을 공부해보신 분이라면 논리연산자들에 익숙할 것인데

비트마스크에서도 이러한 논리연산자들을 사용한다.

 

1. AND 연산 : &

A와 B 둘다 참 ex) 1 & 1 => 1

2. OR 연산 : |

A나 B 하나라도 참 ex) 0 & 1 =>1

3. XOR 연산 : ^

둘 중 하나만 참 ex) 1 & 1 => 0

4. NOT 연산: ~

참이면 거짓으로, 거짓이면 참으로 ex) 1=>0

5. shift 연산: >> or <<

비트들을 왼쪽이나 오른쪽으로 이동시킴 ex) '1001' >>2 => '0010'

 

 

 

비트마스크를 활용한 알고리즘 문제 풀이 예시

https://hidemasa.tistory.com/164

[LeetCode/리트코드] #1178. Number of Valid Words for Each Puzzle[파이썬(python)/Bitmask/비트마스크]