[알고리즘] 비트마스킹(BitMasking) 이란?

백준 풀고 동생과 코드 리뷰 하던 중, 동생이 내가 푼 문제를 보고 "이거 비트마스킹? 그걸로 푸는거 아닌가?" 라고 해서 궁금해서 찾아본 비트마스킹의 정의. 몰랐는데 알고리즘 단골 문제 유형 중 하나인 것 같다...!

---

비트마스킹 (BitMasking) 

비트마스킹 알고리즘 (2진수 표기법의 특징을 활용)
* 비트마스킹 : 컴퓨터가 내부에서 모든 자료를 이진수로 표현하는 것을 이용해 정수의
* 이진수 표현을 자료구조로 쓰는 기법이다.
* 더 빠른 수행시간, 더 간결한 코두, 더 적은 메모리 사용 효과를 볼 수 있다.

 

비트 연산자

& : 모든 비트를 AND 연산한다. (둘다 1이면 1, 아니면 0)
* | : 모든 비트를 OR 연산한다. (둘다 0이면 0, 아니면 1)
* ^ : 모든 비트를 XOR 연산한다. (둘다 다르면 1, 아니면 0)
* ~ : 모든 비트를 NOT 연산한다. (반대로)
* << : a 를 b 비트 만큼 왼쪽으로 시프트
* >> : a 를 b 비트 만큼 오른쪽으로 시프트

😏✨ 비트마스킹으로 집합을 쉽게 표현할 수 있다!!

 

집합의 표현

비트마스크로 집합을 쉽게 표현할 수 있다. (가장 대표적이고 중요한 사례이다.)
* "하나의 bit 가 하나의 원소"를 의미한다.
* 가령, {a,b,c,d,e,f,g} 집합이 있을 때, 우리는 원소의 개수만큼의 비트로 이 집합을 표현
* 할 수 있다.

 * { 0, 1, 2, 3, 4 } => 11111
 * { 1, 2, 3, 4 } => 11110
 * { 1, 2, 4 } => 10110
 * { 2, 4 } => 10100
 * { 1 } => 00010

그리고 해당 집합을 2진수로 나타낸 것을 10진수로 표현할 수 있다.
 * { 2, 4 } => 10100 => (2^4 * 1) + (2^2 * 1) = 20
 * { 1 } => 00010 => (2^1 * 1) = 2

 

집합 원소 다루기

📌 공집합, 채운 집합 

공집합 : A = 0;
꽉찬 10 개 집합 : A = (1 << 10) -1;

 

📌 A집합에 특정 원소 추가하기

1010 로 표현하고 있을 때, i번째 비트의 값을 1로 어떻게 변경할 수 있을까?
i 가 2 일때, 결과는 1110을 원한다.

해당 방법은 다음과 같다.

1010 | (1 << 2);

// 1. 먼저 시프트 연산으로 2번째 비트만 1로 할당되어 있는 이진수를 만든다.
// (1 << 2) : 0001 -> (앞에 2비트 공간 메모리 데이터 사라짐) -> 0100 (남는 오른쪽 2자리 채움)
// 1010 | 0100 => 1110 (그리고 OR 을 해준다.)

 

📌 A집합에 특정 원소 수정하기
이번에는 2번째 비트 값을 0으로 변경한다.

1110 & ~1 << 2

 

📌 A집합에 있는 i번째 비트 값 알 수 있는 방법

A & (1 << i)
ex) 3번째 비트 = 1010 & (1 << 3)

 

📌 A집합에서 i번째 원소 삭제하기
bit 를 항상 0으로 만드는, AND 연산이 필요하다.

1010 & ~(1 << k);

 

비트마스킹 대표 문제 : 외판원 순회

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다.