[파이썬python] 백준 11723번 - 비트마스킹

백준 11723번 집합문제를 풀어보겠습니다.

11723번 문제는 다양한 풀이가 있습니다. 

자료구조를 이용하는 풀이와 그리고 제목에도 언급한 것 처럼 비트마스킹을 이용한 풀이가 있습니다.

저는 비스마스킹을 연습해 볼 기본적인 문제를 찾다가 이 문제를 발견했는데요.

비트마스킹이 무엇인지, 비스마스킹을 어떻게 활용하는지 알고 싶으시다면 끝까지 집중해주세요!

비트마스킹을 사용하면 메모리를 절약할 수 있어서 메모리 제한이 낮은 문제에서 필수입니다. 

문제 요약)

비어있는 공집한 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add  x : S에 x를 추가한다. (1<=x<=20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x : S에서 x를 제거한다. (1<=x<=20) S에 x가 없는 경우에는 연산을 무시한다.
• check x : S에 x가 있으면 1을, 없으면 0을 출력한다. (1<=x<=20)
• toggle x : S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.(1<=x<=20)
• all : S를 {1,2,...,20}으로 바꾼다.
• empty : S를 공집합으로 바꾼다.

풀이)

비트마스크는 알고리즘이라기 보단 bit를 이용한 테크닉에 가깝습니다.

즉, 1과 0으로 정보를 나타내는 것인데, 이것으로 True/False 또는 on/off를 나타낼 수 있습니다. 

1과 0으로 정보를 나타낸다? 뭔가 생각나시는 단어가 있으신가요? 네 바로 이진법이 그러합니다!

비트마스크는 이진법이다 라고 생각하시면 되겠습니다. 

 

이제는 비트 연산에 대해 알아보겠습니다. 

그중에서 비트마스킹에서는 시프트 연산을 이해하는 것이 제일 핵심이라고 생각합니다. 

처음 들어보신다면 어려우실 수 있습니다. 천천히 이해해보도록 하겠습니다.

시프트 연산에는 2가지가 있습니다. 

왼쪽시프트'<<' 와 오른쪽시프트 '>>' 입니다.

화살표방향으로 비트를 옮긴다라고 생각하시면 되는데요.

보통 알고리즘 문제에서는 "1 << num"의 형태처럼 왼쪽시프트에

왼쪽에는 1이 오고, 오른쪽에는 입력으로 받는 숫자를 위치시킵니다.

이게 무슨 말이냐면 "1비트를 num만큼 왼쪽으로 이동시킨다"라는 뜻입니다.

 

만약에 num이 5라고 하면 "1 << 5"는 1비트를 5만큼 왼쪽으로 이동시킨다라는 뜻으로

즉, 1 ->  100000 로 이진법으로 1이였던 수가 100000이 됩니다. 

 

나머지 비트연산은 다음과 같습니다.

나머지 비트연산은 아래 표를 보시면 금방 이해할 수 있습니다..

AND연산 (&)	두 비트가 모두 1일 때 1을 반환	1010 & 1111 = 1010
OR연산 (|)	모두 1또는 하나라도 1일 때 1을 반환	1010 | 1111 = 1111
XOR연산 (^)	두 비트가 서로 다르면 1을 반환	1010  ^ 1111 = 0101
NOT연산 (~)	비트 값을 반전하여 반환	~1010 = 0101

이런걸 도대체 어떻게 써먹나라고 생각하실 수 있는데요.

문제에서 x의 범위는 1 <= x <= 20입니다.

따라서 0과 1로 1부터 20까지의 수가 존재하냐 안하냐로 비트마스킹을 이용하여 나타낼 수 있습니다.

000 000 000 000 000 000 000 맨 오른쪽을 제외하고 1~20까지 숫자가 있으면 1, 없으면 0으로 나타낼 수 있습니다.

ex . 111001 : 1, 2는 없고, 3,4,5는 있고, 6부터 20까지는 없다.  

 

이제 본격적으로 문제를 풀어보도록 하겠습니다. 

가장 간단한 empty와 all을 먼저 보겠습니다.

empty는 0 all은 111 111 111 111 111 111 111을 대입하면 됩니다. 

 

add x는 x가 없으면 x를 추가하고 있으면 무시하는 명령어입니다.

(1 << x)를 하면 x+1자리만 1이 들어가서 x가 있다는 것을 표현할 수 있다고 위에서 언급했었는데요. 

아이디어 : 0(없으면) ? 1 -> 1(있게한다) / (원래있으면) 1 ? 1 -> 1 (무시)  ==> OR연산

따라서 OR연산을 한다면 x+1자리는 1이기 때문에 항상 결과값은 1이 나옵니다. 

따라서 x가 없었으면 0 | 1 = 1이 되어 x가 추가되고, 있었다면 1 | 1 = 1이 되어서 이미 있는 경우로 연산이 무시됩니다.

즉, s = s | (1<<x) 로 표현할 수 있습니다.

 

remove x는 x가 있으면 x를 제거하고 x가 없으면 무시하는 명령어입니다.

위에 add 를 이해하셨다면 잠시 멈추시고 먼저 비스마스킹 식을 떠올려보시길 바랍니다.

 

써보셨나요? 그렇다면 글을 이어가겠습니다. 사실 remove가 제일 어렵습니다.

마찬가지로 (1 << x)로 x+1자리만 1이 들어가서 x를 표현합니다.

아이디어 : 1(있으면) ? 1  -> 0(없애고) / 0(원래없으면) ? 1 -> 0 (무시)  ==> ?

여기에 해당하는 비트 연산이 없다면 (1 << x)에 ~를 붙이고 생각해보겠습니다.

1 ? 0 -> 0 / 0 ? 0 -> 0 ==> AND연산

따라서 s = s & ~(1<<x)로 표현할 수 있습니다. 

 

check x는 x가 있으면 1, 없으면 0을 출력하는 명령어입니다.

1(있으면) ? 1 -> 1 / 0(없으면) ? 1 -> 0 ==> AND연산

따라서 if s & (1 << x)로 값이 1이면 1출력, 0이면 0출력을 하면 됩니다.

 

toggle x는 x가 있으면 x제거 , 없으면 x를 추가하는 명령어입니다.

1(있으면) ? 1 -> 0(제거) / 0(없으면) ? 1 -> 1(추가) ==> XOR연산

따라서 s = s ^ (1 << x)입니다.

 

정답코드)

import sys
input = sys.stdin.readline
m = int(input())
s = 0b0

for _ in range(m):
    order = input()
    try:
        com,num = order.split()
        num = int(num)
        if com == 'add':
            s = s | (0b1 << num)
        elif com == 'remove':
            s = s & ~(0b1 << num)
        elif com == 'check':
            if (s&(0b1<<num)):
                print(1)
            else:
                print(0)
        elif com == 'toggle':
            s = s ^ (0b1 << num)

    except:
        if order == 'all':
            s = 0b111111111111111111111
        elif order == 'empty':
            s = 0b0

앞에 숫자앞에 0b을 붙이면 이진수 연산을 할 수 있습니다. 

try, catch문을 통해 입력값이 2개일 때와 아닐 때를 나누었습니다.

 

비트마스킹을 이용하여 백준 11723번을 풀어보았습니다.

비트마스킹에 대한 설명과 어떻게 비트마스킹을 이용하여 문제를 풀 수 있는지에 대해 말씀 드렸습니다.

비트마스킹에 대한 감을 잡으셨길 바라면서

저도 비트마스킹을 활용한 다른 좋은 문제를 접하게 된다면 또 풀이를 남기도록 하겠습니다.

 

그럼 도움이 되셨다면 공감과 댓글 그리고 구독을 부탁드립니다.!!

 

+비트연산에 대해 좀더 심도있는 공부를 하시고 싶으시다면 다음 게시물을 참고해주세요!

2022.02.12 - [이것저것 개념] - Crash Course #3 부울연산과 논리게이트

Crash Course #3 부울연산과 논리게이트