[백준 파이썬] 11723 집합

📌문제 출처

백준 단계별 문제풀이 : 동적계획법3
https://www.acmicpc.net/problem/11723

11723번: 집합

❓ 문제

 

📗 풀이 코드

- list 자료 구조 활용

input = open(0).readline

def solution():
    s = [0]*21 # 1부터 20까지의 정수를 연산하기 위함
    for _ in range(int(input())):
        ord = input().split()
        if len(ord)==2 :
            x = int(ord[1])
        ord = ord[0]
        if ord == 'add':
            s[x] = 1
        elif ord == 'remove':
            s[x] = 0
        elif ord == 'check':
            print(1 if s[x] else 0)
        elif ord == 'toggle':
            s[x] = 0 if s[x] else 1
        elif ord == 'all':
            s = [1]*21
        else :
            s = [0]*21
            
if __name__ == '__main__':
    solution()

 

- 비트 연산자 활용

input = open(0).readline

def solution():
    s = 0
    for _ in range(int(input())):
        ord = input().split()
        if ord[0] == 'all':
            s = (1<<20)-1 # 1 <= x <= 20 이므로
        elif ord[0] == 'empty' :
            s = 0
        elif ord[0] == 'add':
            s |= (1<<(int(ord[1])-1))
        elif ord[0] == 'remove':
            s &= ~(1<<(int(ord[1])-1))
        elif ord[0] == 'check':
            print(0 if not s&(1<<(int(ord[1])-1)) else 1)
        else : # toggle의 경우
            s ^= (1<<(int(ord[1])-1))
if __name__ == '__main__':
    solution()

✍ 비트마스크란?

정수의 이진수 표현을 자료 구조로 활용하는 방법으로, 메모리 사용량이 적고 수행 시간이 빠르기때문에 주로 사용한다.

예를 들어 51이라는 정수를 110011이라는 이진수로 나타내는 방법인데, 10자리 정수로도 2^10 개의 수를 나타낼 수 있어서 메모리 확보에 용이하다. 이 비트마스크 자료구조를 활용해서 비트 연산자를 사용할 수 있다.

 또한 이 비트마스크를 통해 집합을 쉽게 표현할 수 있으며, 집합 간의 비교, 원소 추가, 삭제 등의 다양한 연산을 빠르게 수행할 수 있다.

📌 비트연산자 예시

a (51 = 110011(2진수))와 b (37 = 100101(2진수)) 두가지 정수 변수를 가지고 연산을 해보자. 아래 연산은 모두 두 정수 변수를 한 bit씩 차례로 비교하며 연산한다.
연산자	특징	연산 결과
AND 연산(a&b)	해당 비트가 둘 다 1이면 1 아니면 0	a&b = 33
OR 연산(a|b)	해당 비트가 둘 다 0이면 1 아니면 0	a|b = 55
XOR 연산(^)	해당 비트가 둘이 다르다면 1 아니면 0	a^b = 22
NOT 연산(~a)	정수 하나를 입력받아서 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠다.(~x = -(x+1)로 이해)	~a = -52 ~b = -38
시프트(shift) 연산(a<<)	비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다. 움직이고 나서 빈자리는 0으로 채워지게 된다.	a<<1 = 102 b>>2 = 9

* 만약 2진수 변환 결과 자리수가 맞지 않는다면 자리수가 모자라는 2진수 앞에 0을 모자란 개수만큼 붙여서 연산.

  다만 양의 정수&음의 정수 연산에서는 넘치는 자리수는 그대로 냅둔다.

* NOT 연산은 2의 보수 개념이 포함되어 있어 복잡하기에 아래 링크 참조

https://m.blog.naver.com/dlscjs8646/222087018882

파이썬의 비트연산과 보수계산, ~(not)계산