★Bitmasking Intermediate I - 3 Solved★

🔟 bitmasking 연산은 매우 빠른 연산으로 O(1)의 time complexity를 보이는 경우가 많아 많이 쓰이는 기법 중 하나

 

🔟 다만, 0과 1을 이용한 2진수 연산이기 때문에 컴퓨터가 실제로 연산하는 하드웨어적인 성격이 들어가므로 단순 연산보다 좀 더 신경을 써야 함

 

🔟 아래 개념 정리 링크 참조

☀️bitmasking☀️

 

🔟 특히 집합 관련 연산을 사용할 때 bitmasking 기법이 많이 쓰인다. 여러 문제를 통해서 적응하도록 하자

 

🔟 비트 연산자 아래 6개는 필수적으로 remind

---

★ 11723 집합 ★

 

🔟 파이썬 집합 set() 관련 함수(add(), discard(), remove(), clear())를 사용하는 풀이도 존재

 

※ set() 관련 메소드 add(), discard(), remove(), clear(), pop() 모두 time-complexity O(1)을 보여 좋은 성능을 나타낸다. ※

 

import sys
input=sys.stdin.readline
S=set()
for _ in range(int(input())):
    op=input().rstrip()
    o=op.split()[0]
    if o not in ['all','empty']:
        n = int(op.split()[1])      
        if o=='add':S.add(n)
        elif o=='remove':S.discard(n)
        elif o=='check':print(1 if n in S else 0)
        else:S.remove(n)if n in S else S.add(n)
    elif o=='all':S={i for i in range(1,21)}
    else:S.clear()

 

🔟 이제 set()가 아닌, bitmasking으로 code를 표현해보도록 하면,

 

① 1부터 20까지의 수가 각각 집합에 존재한다면, 이진수의 해당 자리수가 1, 존재하지 않는다면 해당 자리수를 0으로 표현

(ex) 1과 3이 집합에 존재한다면 S라는 수를 1010로 표현)

 

※ 1<<num 연산에서, 1이 존재한다면 1<<1 결과로 10으로 표현되므로

이진수 상에서 맨 마지막 자리는 0의 자리수, 1은 오른쪽 기준 두번째 자리수,

2는 오른쪽 기준 세번째 자리수로 설정 ※

(<<연산자의 편의성을 위해 이렇게 전제를 만든 뒤 진행함을 잊지 말자!)

 

② 1부터 20사이의 수 x를 추가하는 add 연산

→ 1010에서 2를 추가한다면 두번째 자리수가 1로 변하면서 1110로 되어야 한다.

→ idea) 기존 1010에서 1을 << 연산자로 수 x에 맞게 옮긴 뒤(0100), 1010과 0100을 or | 연산 결과로 111로 바꾼다.

S=S|(1<<num)

 

③ 1부터 20사이의 수 x를 제거하는 remove 연산

→ 1010에서 3을 제거한다면 세번째 자리수가 0으로 변하면서 0010로 되어야 한다

→ idea) 기존 1010에서 1을 << 연산자로 수 x에 맞게 옮긴 뒤(1000), ~ 연산자를 사용해 1과 0을 서로 바꾼 다음(0110), 1010과 0110을 and & 연산 결과로 0010로 바꾼다.

S=S&~(1<<num)

 

④ 1부터 20사이의 수 x가 있는 지 확인하는 check 연산

→ idea) 1010에서 3이 존재하는 지 알고 싶다면, 기존 1010에서 1을 << 연산자로 수 x에 맞게 옮긴 뒤(1000), 1010과 1000을 and & 연산을 진행해 준다. 만약 존재한다면 & 연산으로 1과 1의 결과 1이 나오고, 존재하지 않는다면 1과 0의 결과 0이 나온다.

1 if S&(1<<num) else 0

 

⑤ 1부터 20사이의 수 x가 집합에 있으면 삭제, 없으면 추가하는 toggle 연산

→ idea) 1010에서 3이 존재한다면 삭제, 3이 없다면 추가하고 싶다면, 기존 1010에서 1을 << 연산자로 수 x에 맞게 옮긴 뒤(1000), 1010과 1000을 xor ^ 연산을 진행해준다. ^ 연산은 1과 0 서로 다르다면 1, 0과 0 또는 1과 1이라면 0을 출력해주는 연산이다.

→ (1) 넣고 싶은 수의 자리수에서(1), 원래 수에 만약 없을 경우(0), xor 연산 결과(0과 1) 1이 되어 생기고

→ (2) 넣고 싶은 수의 자리수에서(1), 원래 수에 만약 있을 경우(1),  xor 연산 결과(1과 1) 0이 되어 사라진다.

S=S^(1<<num)

 

⑥ 모든 수가 집합에 존재하게 만드는 all 연산 / 모든 수가 존재하지 않게 만드는 empty 연산

→ idea) 1부터 20까지 모든 수가 존재하는 이진수는 111111111111111111110이다. 이는 1을 21번째 자리수로 옮긴 결과(1<<21; 1000000000000000000000)에서 2를 빼면 원하는 이진수 111111111111111111110가 나온다. ((1<<21)-2)

S=(1<<21)-2

 

※ 주의 ※

<<의 우선순위가 뺄셈(-)보다 낮으므로 반드시 괄호를 해야 한다!

 

→ idea) 모든 수가 존재하지 않으려면 모든 자리수가 0이므로 S=0

S=0

 

🔟 위 add, remove, check, toggle, all, empty 연산에 맞게 bitmasking으로 code를 짜보면 정리하면 아래와 같다

import sys
input=sys.stdin.readline

S=0

for _ in range(int(input())):
    op=input().rstrip()
    o=op.split()[0]
    if o not in ['all','empty']:
        num = int(op.split()[1])
        
        if o=='add': #S에 x추가
            S=S|(1<<num)
        elif o=='remove':#S에 x제거
            S=S&~(1<<num)
        elif o=='check':#S에 x가 있으면 1, 없으면 0 출력
            print(1 if S&(1<<num) else 0) #0b0이면 False, 1이상이면 True
        else:#toggle S에 x가 있으면 x제거, 없으면 x 추가
            S=S^(1<<num)
    elif o=='all':S=(1<<21)-2
    else:#empty
        S=0

---

★ 14569 시간표 짜기 ★

 

import sys
input=sys.stdin.readline
l=[]
for _ in range(int(input())):
    yonsei_class=list(map(int,input().split()))
    class_code=0
    for i in range(1,yonsei_class[0]+1):
        class_code=class_code|(1<<yonsei_class[i])
    l.append(class_code)
for student in range(int(input())):
    student_empty=list(map(int,input().split()))
    student_empty_code=0
    subject=0
    for i in range(1,student_empty[0]+1):
        student_empty_code=student_empty_code|(1<<student_empty[i])
    for code in l:
        if code == (code&student_empty_code): subject+=1
    print(subject)

 

🔟 bitmasking 기법을 사용하면 code 실행 시간을 확실히 단축 시킬 수 있다(타 풀이 실행 시간보다 훨씬 적게 나왔음)

 

🔟 

① 먼저 각 과목별로 class_code를 만든다

(ex) 해당 과목이 2,3교시에 수업한다면 class_code는 2진수로 1100으로 표현)

→ 그리고 모든 과목의 class_code를 l list에 넣음

class_code=class_code|(1<<yonsei_class[i])

 

※ << 연산자와 기존 class_code와의 | 연산자를 사용해 class_code를 완성 ※

 

② 동일한 방식으로 이제 각 학생별 student_empty_code를 만든다

(ex) 예를 들어 한 학생은 2,3교시에 쉰다면 student_empty_code는 2진수로 1100으로 표현)

student_empty_code=student_empty_code|(1<<student_empty[i])

 

③ 이제 class_code와 student_empty_code와 비교

(ex) class_code가 1100이고, student_empty_code가 11100이라면, & 연산자 결과 1100 즉 class_code가 된다. 이 뜻은 기존 class_code에서 1이 있는 자리에 학생이 쉰다면, 즉 1이 있다면 1 & 1 결과로 계속 1이 되어 남게 됨. 따라서 class_code로 그대로 남는 다면, 해당 학생은 이 class를 들을 수 있다는 뜻!)

if code == (code&student_empty_code): subject+=1

---

★ 1094 막대기 ★

print(bin(int(input()))[2:].count('1'))

 

🔟 주어진 숫자가 2의 제곱수에 해당되는, 몇 개의 나무 종류로 X를 나타낼 수 있는 지 알아보는 문제. 예를 들어 23은 이진수로 나타냈을 때 10111이므로 총 4개의 나무 종류의 합으로 23을 나타낼 수 있다. 따라서 2진수로 나타냈을 때 1의 개수가 정답. 2의 제곱수의 합 표현은 비트마스크 기법을 사용해야 하는 직관 기억

---