#24 비트 마스크(Bit Mask)

  비트 마스크(bit mask)는 이름대로 비트연산을 활용하여 어떤 상태정보를 관리하는 테크닉이다. 

 

 예를 들어 반에 n명의 학생이 있고 각 학생마다 수학여행비를 냈는지 내지 않았는지를 관리해야한다고 하자. 이를 데이터로 표현하는 방법은 여러가지가 있지만 흔히 사용되는 방법은 평범하게 배열을 사용하는 것이다.

submited = [False] * n

# k번 학생이 제출했음을 표시할 때
submited[k] = True

# k번 학생이 제출하지 않았다고 변경할 때
submited[k] = False

# 모두 제출한 것으로 처리할 때
submited = [True] * n

# 아무도 제출하지 않은 것으로 처리할 때
submited = [False] * n

이 방법은 매우 간단하고 실제로 사용하기에도 나쁘진 않지만 명확한 한계가 있다.  만약 모두가 수학여행비를 제출했다거나 아무도 제출하지 않은 상태로 업데이트하려면 일일히 순회하며 바꿔주거나 아예 새로 배열을 생성해야하는데, 이는 O(N)의 시간을 필요로 한다.  

 

 비트 마스크를 사용하면 위와 같은 문제를 해결할 수 있다.  이번엔 수학여행비의 제출여부를 비트마스크로 표현해보자

submited = 0

# k번 학생이 제출했음을 표시할 때
submited |= 1 << k

# k번 학생이 제출하지 않았다고 변경할 때
submited &= ~(1 << k)

# 모두 제출한 것으로 처리할 때
submited = (1 << n) - 1

# 아무도 제출하지 않은 것으로 처리할 때
submited = 0

비트마스크를 사용하여 상태를 관리할 경우 모든 작업이 O(1)로 끝나는 것을 확인할 수 있다.  또한 submited가 차지하는 메모리도 상당히 절약된다.  비트마스크를 사용하여 간단한 문제(https://www.acmicpc.net/problem/11723)를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol11723():
    # 집합
    s = 0
    for _ in range(int(input())):
        # 명령어
        cmd = input().split()
        
        # 명령어에 인자가 없을 경우 - all 또는 empty
        if len(cmd) == 1:
			# all 명령어
            # s의 모든 비트값을 1로 초기화
            if cmd[0][0] == 'a':
                s = (1 << 21) - 1
                
            # empty 명령어
            # s를 0으로 초기화
            else:
                s = 0
               
        # 명령어에 인자가 존재하는 경우 - add, remove, toggle, check
        else:
            # 인자값의 비트마스크
            e = 1 << int(cmd[1])
            
            # add 명령어
            # 인자값의 비트마스크와 집합의 비트마스크를 bitwise-or 연산
            if cmd[0][0] == 'a':
                s |= e
                
            # remove 연산
            # 인자값의 비트마스크에 bitwise-not을 취한 값과 집합의 비트마스크를 bitwise-and 연산
            elif cmd[0][0] == 'r':
                s &= ~e
                   
            # toggle 연산
            # 인자값의 비트마스크와 집합의 비트마스크를 집합의 비트마스크와 bitwise-xor 연산 
            elif cmd[0][0] == 't':
                s ^= e
                
            # 인자값의 비트마스크와 집합의 비트마스크를 bitwise-and 연산한 결과가 0이라면 0
            # 0이 아니라면 1을 출력
            else:
                sys.stdout.write('1\n' if s & e else '0\n')

비트 마스크 기법은 그것 자체로 특별한 알고리즘은 아니지만 동적계획법이나 기타 여러 알고리즘에서 최적화에 도움을 주는 기법이기에 잘 알아두고 넘어가는 것이 좋다.