[알고리즘] 비트마스킹

백준 14391 종이조각 문제를 풀면서 메모리 초과가 계속하여 떴다.

아무리 해도 해결이 되지 않아 검색해보니 비트마스킹이라는 새로운 방법을 쓰는 사람이 많았다.

처음 듣는 방법이지만 메모리를 아낄 수 있는 방법이라 종종 쓸 일이 있을 것 같다.

 

---

비트마스킹

특정 비트를 켜고 끄거나 반전시키기 위해
비트 연산에 사용되는 데이터

위키 백과에 따르면 비트마스크는 비트 연산에 사용되는 데이터로,

다중 비트들을 싱글 비트 연산 작업에서 켜고 끄거나 상호 반전시킬 수 있다.

 

일단 비트 연산들을 알아보겠다.

비트 연산자	설명
&	AND (둘 다 1이면 1 반환)
|	OR (둘 중 하나라도 1이면 1 반환)
^	XOR (둘이 서로 다르면 1 반환)
~	NOT ( 1-> 0, 0->1 반전)
<<	left shift (지정한 수만큼 왼쪽으로 비트 이동)
>>	right shift (지정한 수만큼 오른쪽으로 비트 이동)

 

비트마스킹이란 이러한 비트 연산을 활용한 알고리즘이다.

 

비트마스킹의 장점

1. 시간복잡도가 작음

O(1)의 시간복잡도

2. 짧은 코드

비트 연산자를 사용해서 코드 간결

3. 메모리 부족 해결

 

비트마스킹 활용 방법

 

1. 집합 표현

 

원래는 다이나믹 프로그래밍을 위한 dp 테이블을 만들 때 n개의 원소를 갖는 boolean 배열을 만들지만,

비트마스킹을 이용할 경우 이 테이블을 하나의 정수로 표현할 수 있어 메모리를 절약할 수 있다.

비트가 1이면 원소가 존재한다는 의미, 0이면 존재하지 않는다는 의미를 가진다.

원소가 존재하는 곳만 1로 바꾸어 1과 0으로 이루어진 이진수를 만들 수 있고,

그 수를 정수로 바꾸어 저장하면 용량을 크게 절약할 수 있다.

 

2. 원소 포함여부

A & (1 << k)

 

어떤 원소가 포함되었는지 확인하려면 and 연산을 이용해 그 비트가 1인지 확인하면 된다.

 

3. 원소 추가

A | (1 << k)

집합에 특정 원소를 추가하려면 원소에 해당하는 비트를 1로 바꾼다.

이때는 or 연산을 이용해서 바꿔주는데, 이미 그 원소가 존재하는 경우에는 변화가 없다.

 

4. 원소 삭제

A & ~(1 << k)

 

해당 원소가 존재할 때 and 연산을 이용해 그 원소의 비트를 0으로 바꾸어준다.

그러나 그 원소가 존재하지 않을 때는 다른 원소에 영향을 미칠 수 있어 유의해야 한다.

 

5. 원소 토글

A ^ (1 << k)

 

특정 원소가 존재하면 삭제하고, 없다면 추가하는 방법으로 xor 연산을 이용한다.

 

6. 집합 연산

- A | B 합집합

- A & B 교집합

- A & (~B) 차집합

- A ^ B 합집합 빼기 교집합