비트마스트?
-> 데이터를 저장하는 하나의 방법으로,
컴퓨터는 내부적으로 모든 자료를 이진수로 표현하는데, 이와 같은 특성을 이용하여
정수의 이진수 표현을 자료구조로 쓰는 기법
비트마스크란 ?
컴퓨터는 내부적으로 bit 단위로 연산을 진행.
bit는 0과 1로만 구성되어 있는데 이러한 특징을 이용하여 간결한 코드와 빠른 속도로 활용이 가능.
만약, 10개의 visited를 체크해야 한다면 보통 visited = [False] * 10와 같이 리스트를 많이 사용. 비트마스킹의 경우 아래와 같이 표현하여 하위 주소인 오른쪽부터 0인지 1인지 확인만 하면 됨
visited = 0b00000000
비트마스크의 장점
1. 메모리
32개의 int형 데이터를 저장하는 리스트를 만든다고 하면 약 4 * 32Byte의 공간이 필요.
하지만 비트마스크를 이용하면 4Byte 정수 한개로 데이터 저장 가능.
저장해야할 데이터가 많을수록 비트마스크를 이용하면 메모리 절약에 유용.
2. 연산 속도
비트마스크는 '비트연산자'를 사용하는데, 대부분 O(1)의 공간복잡도를 가짐.
다른 자료구조를 이용하는 것보다 빠르게 연산 처리 가능.
비트 연산자
비트마스크를 수행하기 위해 알아야 할 연산자.
1. | : OR -> 두 비트 중 어느 한쪽이라도 1이면 1
2. & : AND -> 두 비트가 모두 1 이어야 1
3. ~ : NOT -> 1이면 0, 0이면 1
4. ^ : XOR -> 두 비트가 같으면 0, 다르면 1
5. <<: Left Shift -> 비트를 왼쪽으로 밀어냄. 마지막에 추가되는 값은 0
- 1010 << 1 = 0100
- 1010 << 3 = 1000
6. >>: Arithmetic Right Shift -> 부호를 유지한 채로 비트를 오른쪽으로 밀어냄. 첫번째 비트는 유지하고 두번째 비트부터 오른쪽으로 밀어냄. 두번째 비트부터 생긴 빈 곳은 0
- 00000100 >> 1 = 00000010 (4 >> 1 = 2)
- 11111111 >> 2 = 10011111 (-1 >> 2 = -31)
7. >>>: Logical Right Shift -> 무조건 비트를 오른쪽으로 밀어냄. 첫번째 비트에 생긴 빈 곳은 0
- 11111111 >>> 2 = 00111111(-1 >>> 2 = 63)
비트마스킹 실습
비트마스킹 문제 -> 백준 11723 문제
x의 범위는 1부터 20. 따라서 0번째를 0이라고 가정하고, 길이가 21인 비트를 생각하면 됨.
이때 이진수를 자료구조로 생각하면 오른쪽부터 채워지므로, 인덱스를 거꾸로 생각해야함.
원소 추가
집합 S에 원소 x를 추가한다면, S의 x번째 비트만 1로 만들어면 됨.
1 << x은 x번째를 1로 세팅해주는 거라고 생각하면 된다.
S |= (1 << x)
원소 삭제
S에서 x를 삭제한다면, S의 x번째 비트를 0으로 만들어주면 됨.
~(1 << x)는 x번 비트만 0으로 만들고 나머지는 1로 만들어 주는 것이다.
이렇게 해주고 and 연산을 하면 x를 제외한 나머지 비트는 동일한 상태를 유지할 수 있음.
S &= ~(1 << x)
원소 토글
S에서 x가 없으면 추가, 있으면 삭제하는 연산 -> XOR 연산
S ^= (1 << x)
원소 체크
S에 x가 있으면 1, 없으면 0을 출력. -> and 연산
print(1 if S & (1 << int(op[1])) != 0 else 0))
원소 비우기 및 채우기
S = 0 #비우기
S = (1 << 21) - 1 #채우기
