지나가던 개발자
[Algorithm] 비트마스킹 | Python 본문
저번에 백준의 11723번 문제를 이 비트마스킹을 사용해서 풀었었습니다.
https://developer-next-to-you.tistory.com/295
[Python] 백준 11723번(집합) 문제 풀이
import sys S = 0 for i in range(int(sys.stdin.readline())): command = sys.stdin.readline().split() if len(command) == 1: if command[0] == "all": S = (1
developer-next-to-you.tistory.com
비트마스킹이란 기본적으로 정말 간단한 개념입니다.
컴퓨터는 이진수로 생각하죠? 이진수는 0과 1로 이루어져 있습니다. 이 0과 1을 각각 False와 True로 생각하여 연산하는 것이 비트마스킹의 핵심입니다.
그러면 이런 생각이 들 수가 있습니다. "True와 False로 이루어진 배열을 만들면 될 것을 뭐 하러 비트마스킹을 해서 불리안을 계산할까?" 물론 True와 False로 이루어진 배열을 만들어도 비트마스킹을 사용한 것과 동일히 작동할 것입니다. 그렇지만 비트마스킹이 가진 압도적 장점은 빠르고 간결하다는 것입니다.
파이썬에서 "A and B"는 A와 B가 모두 참일 때 True를, "A or B"는 A와 B 중 하나 이상이 참일 때 True를 반환한다는 점은 모두들 알고 계실 것이라고 생각합니다. 비트마스킹 또한 and과 or에 해당하는 연산자가 있습니다.
& 연산자는 and에, | 연산자는 or에 해당되는 연산자로써 &을 사용하면 각 인덱스에서 모두가 1(True)이어야만이 1이 반환되고, |을 사용하면 각 인덱스에서 하나 이상이 1(True)이기만 하면 1이 반환됩니다.
1111 & 1010 = 1010
1111 | 1010 = 1111
또, 비트마스킹을 할 때에는 ^(xor)이라는 연산자 또한 존재합니다. ^은 대응하는 두 비트가 다를 때에 1을 반환합니다.
1111 ^ 1010 = 0101
비트마스킹에는 Shift를 할 수 있는 연산자도 존재합니다. <<은 왼쪽으로, >>는 오른쪽으로 비트를 쉬프트합니다. 쉬프트한다는 말이 무슨 말인지 이해가 안 가신다면, A << B일 때 <<은 A*(2^B)를, >>은 A/(2^B)를 의미한다고 생각하시면 됩니다. (여기서 ^은 xor이 아니라 거듭제곱입니다!!)
또, (1 << N)은 N번째를 1로 정해주는 것입니다!
00001010 << 2 = 101000
00001010 >> 2 = 000010
~은 비트를 반전합니다.
~1010 = 0101
이 글을 쓰는 데 도움이 되었던 자료:
'Algorithm' 카테고리의 다른 글
| [Algorithm] 분할 정복을 이용한 거듭제곱 | 빠른 거듭제곱 | Python (0) | 2022.10.22 |
|---|---|
| [Algorithm] 오일러 피 함수(Euler's phi function) | 서로소인 자연수의 개수 구하기 | Python (1) | 2022.10.22 |
| [Algorithm] 카라추바 알고리즘 | 빠른 곱셈 | Python (1) | 2022.09.09 |
| [Algorithm] 빅오(Big-O) 표기법으로 시간 복잡도 나타내기 (0) | 2022.08.29 |
| [Algorithm] 1부터 n까지의 합이 {n(n+1)}/2인 이유 (0) | 2022.01.17 |
