🔴 개요
컴퓨터는 내부적으로 이진수를 표현하는 비트를 사용해 연산을 수행합니다. 따라서 고수준의 언어에서 비트 연산을 활용해 어떤 연산을 구현한다면, 같은 연산이어도 더 효율적으로 동작하게 만들 수 있습니다.
비트 연산을 활용해 특정 연산을 수행하는 것을 비트 마스킹 이라고도 합니다. 이러한 비트 마스킹은 주로 집합을 표현하는 데 많이 쓰입니다.
예를 들어 [1, 2, 3]의 수 중 1과 3이 집합에 표현되어있음을 비트 101로 나타낼 수 있습니다. 이처럼 집합에서 하나의 수에 대한 표현 여부를 결정할 때 하나의 비트가 활용되는 만큼 매우 많은 수의 포함 여부를 표현할 수는 없습니다. 하지만 수의 범위가 비트로 표현하기 충분히 작다면, 어느 연산보다 효율적인 성능으로 집합을 표현할 수 있습니다.
🟠 핵심 : shift 연산
비트로 집합을 표현하기 위한 핵심은 shift 연산입니다. a <<(>>) b 연산은 a 비트를 b만큼 왼쪽(오른쪽)으로 이동시키는 연산입니다. 이 연산이 핵심인 이유는 우리가 만약 [1, 2, 3]의 수 중 3번째 수가 포함되었다고 표현하기 위해서는 3번째 수만 1인 비트열을 만들어 내어야 하기 때문입니다.
이 때 비트연산 0b1 << 3 을 수행하면 1이 3만큼 왼쪽으로 이동하여 0b1000 가 됩니다. (후술하겠지만, 파이썬에서 앞에 0b가 붙으면 2진수를 표현하는 것입니다.)
🟡 집합 연산
그렇다면 본격적으로 이를 활용해서 집합 연산을 구현해보겠습니다. 현재 집합을 나타내는 비트는 001로 [1, 2, 3] 중 1만 포함되어있다고 가정합니다. 또한 [1, 2, 3] 중 1, 2, 3을 각각 0번째, 1번째, 2번째 수라고 지칭하고, 특정 위치의 비트를 num번째 비트라고 지칭하겠습니다.
✚ add
위에서와 같이 [1, 2, 3]에서 2번째 수인 3을 포함시키려면 001인 비트를 101으로 바꿔줘야 합니다. 이를 위해서는 위에서 해당 위치의 비트만 1인 비트열이 필요하다고 했는데요, 이 두 비트를 OR(|) 연산하면 되겠습니다.
이처럼 두 비트 중 하나만 1인 경우 1을 반환하는 OR 연산의 특성을 활용해서 add 연산을 표현할 수 있습니다. 이를 일반화 해서 set이라는 집합에 num번째 수를 포함시킬 때 아래와 같이 나타낼 수 있습니다.
set = set | 1 << num
− remove
반대로 집합에서 수를 제거하는 것을 어떻게 표현할 수 있을까요? 101을 001로 다시 바꿔줘야 합니다. 위와는 반대로 num번째 비트만 0인 비트열과 집합 비트열을 AND(&) 연산 하면 원본 집합 비트열은 그대로 유지하고 num번째 비트만 0으로 만들어낼 수 있습니다.
num번째 비트만 0인 비트열은 num번째 비트만 1인 비트열을 ~ 연산자로 반전시키면 됩니다.
set = set & ~(1 << num)
✔ check
집합이라면 num번째 수가 포함되어있는지 확인하는 것도 필수입니다. 집합 비트열에서 num번째 비트가 1인 것만 확인하면 되니, num번째 비트만 1인 비트열과 and연산을 수행하면 됩니다.
이제 아래와 같이 결과 비트열이 0인지 1인지만 판단하면 됩니다
set & (1 << num) ? true : false
⏣ toggle
마지막으로 집합 비트열에 num번째 수가 존재하면 이를 제거하고, 존재하지 않는다면 포함시키는 toggle 연산을 표현해보겠습니다. 두 피연산 비트가 서로 다를 때 1을 반환하는 연산자인 XOR(^)를 활용하면 좋을 것 같습니다.
위처럼 num번째 비트만 1인 비트열과 xor 연산을 수행하면 num번째 부호의 비트만 반전시킨 비트열을 얻어낼 수 있습니다.
set = set ^ (1 << num)
🟢 파이썬으로 구현해보기
이처럼 비트 연산을 제대로 이해하고 있다면 생각보다 쉽게 구현이 가능합니다. 저는 이를 파이썬 클래스로 구현해보았습니다. 생성자에서 클래스 변수로 빈 비트열을 생성하고, 각 클래스 메서드에서는 빈 비트열에 입력으로 들어온 수와 비트 연산을 수행하여 집합 연산을 표현했습니다.
class BitSet:
"""
비트마스킹을 활용한 집합 표현 자료구조
"""
def __init__(self) -> None:
"""
생성자, 초기 빈 비트열 생성
"""
self.bit = 0b0
def add(self, v: int) -> None:
self.bit |= 0b1 << v
def remove(self, v: int) -> None:
self.bit &= ~(0b1 << v)
def check(self, v: int) -> None:
print(1 if self.bit & (0b1 << v) else 0)
def toggle(self, v: int) -> None:
self.bit ^= 0b1 << v본인 나름대로 비트열을 활용해 집합을 표현해보며 연습하는 것도 큰 도움이 될 것 같습니다.
BOJ-11723 집합 문제에서 이를 연습해볼 수 있습니다. 위 클래스를 활용해서 문제에 그대로 적용 가능하고, 몇 개의 메서드만 더 구현하면 됩니다
🔵 응용
외판원 순회 문제(TSP)에서 비트 마스킹을 활용한 동적 계획법을 활용해 단순 그래프 탐색보다는 훨씬 효율적으로 문제가 가능합니다. 동적 계획법의 메모이제이션 과정에서 순회해야 하는 도시가 5개라고 가정한다면 5개의 도시를 방문하는 2^5 가지의 상태를 비트마스킹을 활용해 보다 효율적으로 표현할 수 있습니다.
다음 포스팅에서는 이 문제에 대해서 다뤄보겠습니다.
✏️ 감사합니다. 본 포스팅의 이론 정리 및 코드에 대한 질의와 피드백은 환영입니다!
