알고리즘 문제들을 풀다보면 대부분 시간복잡도를 우선적으로 보지만 공간복잡도가 눈에 띄게 제한적인 문제들도 있다. 이럴때 사용할 수 있는 비트연산을 활용한 비트 마스킹을 소개한다.

비트 연산자

파이썬에서는 비트 연산자를 제공한다.

• & : and
• | : or
• ~ : not
• ^ : XOR

구체적인 비트연산자는 밑에 링크에서 알아볼 수 있다.
https://dojang.io/mod/page/view.php?id=2460

비트 마스킹

만약 1~5의 값을 받아 리스트에 저장하는 문제를 생각해보자

일반적으로 [1] 이나 [5]와 같은 형태로 값을 받을 것이다.
하지만 이는 아래와 같이 boolean 자료형을 활용해 나타낼 수 도 있다.
[False, False, False, False, True] = 5
이런 저장방법은 메모리면에서 아주 효율적이다.

만약 이런 방식을 이진법으로 적용하면 어떨까?
예를 들어 1과 5를 담은 리스트는 10001(5bit)과 같이 표현될 수 있다. 따라서 이런 이진 비트를 가지고 조작하면 리스트를 사용하여 값을 저장하는 것보다 훨씬 메모리면에서 이득이다.(심지어 비트연산은 속도도 빠르다.

이렇게 이진수의 표현을 자료구조로 사용하는 방법을 비트 마스킹이라고 한다.

집합

코테에서 비트마스킹의 주된 사용처는 집합을 구현하는데에 사용한다.

예제 - 백준 11723

https://www.acmicpc.net/problem/11723
집합 추상자료형을 코드로 구현하는 문제로서 크게 두 가지 풀이로 풀어볼 수 있다.

집합 자료형

import sys

def input(): return sys.stdin.readline().strip()

M = int(input())

my_set = set()

for _ in range(M):
    tmp = list(input().split(' '))
    
    if len(tmp) == 1:
        if tmp[0] == 'all':
            my_set = set([i for i in range(1, 21)])
        else:
            my_set = set()
        continue
    command, num = tmp[0], tmp[1]
    num = int(num)
    if command == "add":
        my_set.add(num)
    if command == "remove":
        my_set.discard(num)
    if command == "check":
        print(1 if num in my_set else 0)
    if command == "toggle":
        my_set.discard(num) if num in my_set else my_set.add(num)

비트 마스킹 (메모리와 속도면에서 우수하다)

import sys

M = int(input())

bit = 0
for _ in range(M):
    command = sys.stdin.readline().rstrip().split()

    if len(command) == 1:
        if command[0] == 'all':
            bit = (1 << 20) -1
        else:
            bit = 0 
        continue
    
    command, num = command[0], command[1]
    num = int(num) - 1
    
    if command == "add":
        bit |= (1 << num)
    if command == "remove":
        bit &= ~(1 << num)
    if command == "check":
        print(0) if bit & (1 << num) == 0 else print(1)
    if command == "toggle":
        bit = bit ^ (1 << num)