[알고리즘] 비트마스크(BitMask)

비트마스크란?

비트마스크(Bitmask)는 이진수의 비트를 사용해 여러 상태나 조합을 효율적으로 표현하는 기법입니다. 각 비트는 특정한 상태를 나타내며, 비트 연산을 통해 다양한 조합을 처리할 수 있습니다. 비트마스크는 조합 문제나 상태 추적 문제에서 특히 유용하게 사용됩니다.

 

장점

1. 메모리 효율성: 비트를 사용해 여러 상태를 간단하게 저장할 수 있어, 메모리 공간을 절약할 수 있습니다.
2. 속도: 비트 연산은 빠르기 때문에, 대량의 데이터를 신속하게 처리할 수 있습니다.
3. 조합 관리: 비트마스크를 사용하면 여러 상태를 조합하는 문제를 쉽게 해결할 수 있습니다.
4. 코드의 간결성: 비트 연산을 사용하면 코드가 간결해지고 가독성이 좋아질 수 있습니다.

단점

1. 이해의 어려움: 비트마스크의 개념이 초보자에게는 다소 복잡하게 느껴질 수 있습니다.
2. 한계: 비트 수가 많아지면 메모리 사용이 급격히 증가할 수 있습니다.
3. 디버깅의 어려움: 비트 연산으로 작성된 코드는 디버깅이 복잡할 수 있으며, 상태 추적이 어려운 경우가 많습니다.

 

예제

신약 찾기 문제

문제 설명

100가지 종류의 신약 중 하나만 정상이고, 나머지는 모두 치명적입니다. 제한된 시간 내에 토끼에게 신약을 먹여 정상 신약을 찾아야 합니다. 이때 필요한 최소한의 토끼 수를 구하는 것이 문제의 핵심입니다.

해결 방법

1. 신약의 비트 표현:
   • 신약 100가지를 비트로 표현할 수 있습니다. 각 신약은 비트의 한 위치로 표현되며, 토끼가 먹는 신약의 조합을 비트마스크로 관리합니다.
2. 필요한 토끼 수 계산:
   • 정상 신약을 찾기 위해 필요한 토끼 수는 신약의 개수를 2의 몇 승으로 표현할 수 있는지를 통해 결정됩니다. 즉, log2(100)을 계산하여 필요한 최소 비트 수(토끼 수)를 구합니다.
3. 비트마스크 활용:
   • 각 토끼는 서로 다른 조합의 신약을 먹고, 한 시간 후 살아남은 토끼의 조합을 통해 정상 신약을 판단할 수 있습니다.

 

알고리즘 코드

import math

def find_min_rabbits(pills):
    # 신약의 개수
    n = len(pills)
    
    # 비트마스크로 구별할 수 있는 최소 토끼 수는 log2(n) 값을 올림한 것
    rabbits_needed = math.ceil(math.log2(n))
    
    return rabbits_needed

# 신약의 개수 100개
pills = list(range(100))
print("필요한 최소 토끼 수:", find_min_rabbits(pills))