비트마스크 알고리즘

비트마스크

비트마스크(Bitmask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다.

비트마스크를 사용하면 더 빠른 시간 내에 연산을 해결하는 경우가 있다.

예를 들어, 2의 50승을 구해야 하는 문제가 있다고 하자.

이 경우 for문을 50번 돌려서 2를 계속 곱해나가야 한다 생각할 수 있지만, 비트마스크를 사용하면 1 << 50 연산 한 번으로 해결된다.

또한, 가장 큰 장점으로는 메모리 사용량이 적다는 것이다.

예를 들어, bit가 10개인 경우, 각 bit당 1 또는 0, 두 가지 경우를 가지기 때문에 2의 10승가지의 경우를 10bit 이진수 하나로 표현이 가능하다.

이처럼 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에, 메모리 측면에서 매우 효율적이다.

&, |, ^, ~, << 등 일반적인 비트 연산자는 알고 있어도, 이를 어떻게 활용해야 하는지 잘 모르는 경우가 많다.

알고리즘 문제에서는 보통 집합을 표현하는데 비트마스크를 많이 사용한다. '하나의 bit가 하나의 원소'를 의미하며, bit가 켜져 있으면 해당 원소가 집합게 포함되어 있다는 의미이고, 꺼져 있으면 포함되어 있지 않다는 의미이다.

이를 N개의 boolean 원소를 갖는 배열을 사용하는 것이 아닌, 비트마스크를 사용하면 정수 하나로 표현이 가능하기 때문에, 메모리를 크게 아낄 수 있다.

예를 들어, S라는 변수를 집합이라고 가정하고, 집합의 총 원소의 개수를 10개(0 ~ 9)라고 가정하자.
코드는 python 기준이다.

참고자료