자료구조 | 알고리즘

비트마스크 (BitMask), 비트마스크 문제

seulll 2024. 11. 4. 17:26

비트마스크란? 

이진수를 사용하는 컴퓨터의 연산 방식을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법

이진수 0 또는 1을 사용하므로 하나의 비트가 표현할 수 있는 경우는 두 가지이다.

 

비트마스크의 장점

1. 수행 시간이 빠르다. 

비트마스크 연산은 비트 단위로 이루어져 대부분 O(1) 시간 복잡도로 처리된다. 비트마스크를 사용하면 비트의 개수만큼 원소를 다룰 수 있어, 연산 횟수가 적을 때는 속도 차이가 크지 않지만, 연산이 많아질수록 성능 차이가 확연히 커진다.

 

2.코드가 짧다.

비트 연산자를 사용해 다양한 집합 연산을 한 줄로 작성할 수 있어, 반복문이나 조건문을 사용하는 코드보다 훨씬 간결하게 표현할 수 있다.

 

3. 메모리 사용량이 적다.

비트가 10개면 각 비트가 두 가지 상태를 가질 수 있어서, 총 2^10가지 경우의 수를 10비트 이진수 하나로 표현할 수 있다. 이렇게 다양한 상태를 하나의 값에 담을 수 있으므로 메모리 측면에서 효율적이며, 미리 계산한 많은 데이터를 저장해둘 수 있는 장점도 있다. 따라서 동적 계획법(DP)에서 특히 유용하게 쓰인다.

비트 연산자

비트마스크를 사용하기 위해서는 비트를 조작할 수 있는 다양한 비트 연산자를 활용한다. 이를 통해 두 정수 또는 하나의 정수를 조작하여 새로운 값을 만들어낼 수 있다.

 

1. AND 연산 (&)

두 정수 변수 a와 b를 통해 c를 생성할 때, 각 비트를 비교하여 둘 다 켜져 있는 경우에만 c의 해당 비트를 켠다.
c = a & b

 

2. OR 연산 (|)

AND 연산과 유사하게, 각 비트 중 하나라도 켜져 있으면 c의 해당 비트를 켠다.

c = a | b

 

3. XOR 연산 (^)

두 정수의 해당 비트 중 하나만 켜져 있는 경우에 c의 해당 비트를 켠다. XOR 연산은 같은 값이 있는 비트를 0으로 만드는 데 유용하다.
c = a ^ b

 

4. NOT 연산 (~)

정수 a의 각 비트를 반전하여, 켜져 있는 비트는 끄고 꺼져 있는 비트는 켠다.
 c = ~a

 

5. 시프트(shift) 연산 (<<, >>)

시프트 연산은 a의 비트를 왼쪽 또는 오른쪽으로 지정한 만큼 이동시키고, 빈 자리는 0으로 채운다. 예를 들어 13 (이진수 1101)을 오른쪽으로 1비트 이동시키면 6 (이진수 0110)이 된다.
c = (a << 1)

 

 

- 주의점

 

 

  • 비트 연산자의 우선순위는 비교 연산자보다 낮다.
  • ex) a = (10 & 6 == 2)라면  6==2 가먼저 계산되어 0(false)을 반환하고, 이후 10 & 0을 할당

비트마스크 예제 문제

한 성에 500개의 우물이 있다. 내일 왕실 연회에서 사용될 물을 이 중 한 우물에서 길어올 예정이다. 하지만 갑작스럽게, 500개의 우물 중 1개의 우물에 독이 섞였다는 소식이 전해졌다. 이 독은 마신 지 정확히 12시간 후에 효과가 나타나며, 효과가 나타난 사람은 사망한다. 궁정에는 총 9명의 시음사가 있다. 이 시음사들을 활용하여, 12시간 후에 독이 든 우물을 찾아낼 수 있는 방법을 고안하라. 조건: 시음사들은 모든 우물을 한 번에 마시고, 12시간 후에 상태가 관찰된다. 시음사들에게 한 번에 여러 우물에서 물을 마시게 할 수 있다. 9명의 시음사만을 사용해 정확히 독이 든 1개의 우물을 찾아야 한다. 

 

문제 풀이 

1. 우물 번호 할당

 -  각 우물에 0부터 499까지 번호 할당.

- 이를 이진수로 표현하면 500은 9비트로 표현할 수 있다.

 

2. 비트마스크 활용

- 9명의 시음사 각각을 비트로 생각하고, 우물의 번호를 이진수로 변환한다. 이진수의 각 비트는 시음사가 마실 우물의 여부를 나타낸다. 예를 들어, 우물 번호 23은 이진수로 000000010111이고, 1이 표시된 비트(3, 1, 0번째 비트)에 해당하는 시음사가 그 우물의 물을 마신다.

 

3. 12시간 후 결과 확인

- 12시간 후, 어떤 시음사가 사망했는지를 확인한다. 사망한 시음사의 비트 위치를 조합하여 이진수로 나타내면, 독이 든 우물의 번호를 알 수 있다. 예를 들어, 1번째, 3번째, 5번째 시음사가 사망했다면, 이진수로 000000011010이 되며, 이를 10진수로 변환하면 독이 든 우물의 번호가 26이라는 것을 알 수 있다.