[알고리즘] 비트마스킹에 대해 알아보자

인턴을 하게 되면서 알고리즘 문제를 많이 접하게 되지만,, 나에게는 아직도 알고리즘은 머리 아픈 숙제와 가깝다.
그래도 인턴으로 있으면서 잊어버렸던 전공지식이 되살아나는 중이다. 함께 일하는 분들에게 어찌나 감사한지..

 

이번에는 집합 문제 풀 때 유용하게 사용할 수 있다는 비트 마스킹에 대해 알아보려고 한다.

 

그냥 재귀로 풀면 되는거 아냐?

생각했는데, 비트마스킹을 이용하면 훨씬 간단하고 빠른 속도로 알고리즘을 풀 수 있다는 사실을 배우게 되었다.

 

대학생 때 분명 배웠던 것 같은데..왜 이렇게 익숙해지지 않는지..

 

비트마스킹이란?

비트 마스킹은 정수의 이진수 표현을 자료구조로 사용해서 알고리즘을 효율적으로 구현하는 기법이다. 비트 연산자는 수학적 계산을 넘어서 다양한 문제를 간결하고 빠르게 해결할 수 있도록 도와준다. 특히 집합을 다룰 때 유용하게 사용되며, 정수 하나를 집합의 상태를 나타내는 비트로 사용한다. 예를 들어, 집합에 포함된 원소가 있으면 해당 비트를 1로, 없으면 0으로 설정하는 방식이다.

 

왜 비트 마스킹을 사용할까?

비트 마스킹을 사용하면 빠른 수행 시간, 간결한 코드, 적은 메모리 사용 등의 장점이 있다. 이는 비트 연산을 통해 데이터를 다룰 때의 특성 덕분이다. 집합 연산을 할 때마다 데이터를 하나씩 확인하는 대신, 비트 연산을 사용하면 여러 원소를 한 번에 처리할 수 있기 때문이다.

 

비트 연산자

a&b	AND 연산 둘다 1이면 1, 아니면 0
a|b	OR 연산 둘 다 0 이면 0, 아니면 1
a^b	a의 모든 비트와 b의 모든 비트를 XOR 연산. 둘이 다르다면 1, 아니며 0
~a	a의 모든 비트에 NOT 연산 0이면 1, 1이면 0
a<<b	a를 b비트만큼 왼쪽으로 시프트 ex) a=1=001(2), a<<2 = 100(2) =4
a>>b	a를 b비트만큼 오른쪽으로 시프트 ex) a=4=100(2), a>>2=001(2)=1

 

비트 마스킹 예시

가장 기본적인 예시로, 3개의 원소가 있는 집합을 다룬다고 가정하자. 이 집합을 비트 마스크를 이용해 표현할 것이다. 집합의 원소가 포함되었으면 해당 비트를 1로, 포함되지 않았으면 0으로 설정한다.

 

집합 예시

• 집합 A = {1, 3}
• 집합 B = {2, 3}

이 집합들을 비트 마스크로 표현할 때, 각각을 이진수로 변환할 수 있다.

• 집합 A는 {1, 3}이므로 이진수로 101 (왼쪽에서부터 차례대로 1, 2, 3번째 원소를 나타냄)
• 집합 B는 {2, 3}이므로 이진수로 011

1. 비트마스크로 집합 표현하기

// 집합 A와 집합 B 
let A = 0b101; // {1, 3} 
let B = 0b011; // {2, 3} 

// 집합 A와 집합 B를 비트마스크로 출력 
console.log(A.toString(2).padStart(3, '0')); // "101" 
console.log(B.toString(2).padStart(3, '0')); // "011"

위 코드는 집합 A와 B를 각각 0b101과 0b011로 표현한다. 이진수로 출력할 때 padStart(3, '0')를 사용해서 3자리로 맞춘다.

2. 집합의 합집합 (OR 연산)

집합 A와 B의 합집합을 구할 때, 비트 OR 연산을 사용한다. 합집합은 두 집합에 존재하는 원소들을 모두 포함하는 집합이다.

let union = A | B; // A와 B의 합집합 
console.log(union.toString(2).padStart(3, '0')); // "111"

 

합집합을 구하는 방법은 A | B로, OR 연산을 이용해서 두 집합의 원소를 모두 포함하는 새로운 집합을 만든다. 결과는 0b111로 {1, 2, 3}이 된다.

3. 집합의 교집합 (AND 연산)

교집합은 두 집합에 모두 존재하는 원소들만 포함하는 집합이다. 비트 AND 연산을 사용한다.

let intersection = A & B; // A와 B의 교집합 
console.log(intersection.toString(2).padStart(3, '0')); // "001"​

교집합을 구할 때는 A & B로, 두 집합에 공통으로 포함된 원소들만 남게 된다. 결과는 0b001로 {3}이 된다.

4. 집합의 차집합 (AND, NOT 연산)

차집합은 첫 번째 집합에는 포함되고 두 번째 집합에는 포함되지 않은 원소들만 남기는 집합이다. A & ~B로 구할 수 있다.

let difference = A & ~B; // A에서 B를 뺀 차집합 
console.log(difference.toString(2).padStart(3, '0')); // "100"

차집합은 A & ~B로, B에 포함되지 않은 원소들만 남는다. 결과는 0b100으로 {1}이 된다.

5. 집합의 원소 포함 여부 체크

어떤 원소가 집합에 포함되어 있는지 확인하려면, 비트 AND 연산을 사용해 특정 비트가 1인지 확인한다. 예를 들어, 원소 2가 집합 A에 포함되어 있는지 확인하려면 A & (1 << 1)을 사용한다. 1 << 1은 2번째 비트를 나타낸다.

// 원소 2가 집합 A에 포함되어 있는지 확인 
let element = 2; 
let check = A & (1 << (element - 1)); // A에서 2번째 비트가 1인지 확인 
console.log(check !== 0 ? "포함" : "미포함"); // "미포함"

 

(1 << (element - 1))는 2번째 비트를 1로 만든 값이다. 만약 집합 A에서 이 비트가 1이면 포함되어 있다고 판단한다.

 

 

 

이처럼 비트 마스킹을 사용하면 집합을 표현하고 집합 연산을 효율적으로 처리할 수 있다.

&, |, ^, ~ 등의 비트 연산자를 활용하면 간결하고 빠르게 집합 문제를 해결할 수 있다. 

 

비트마스킹을 이용해 백준 문제를 풀어보면서 차차 적용해나가보자

(사실 요즘 백준은 무슨 후유증 때문에 실버문제도 읽기 힘든 지경이지만..)

https://www.acmicpc.net/problem/11723

https://www.acmicpc.net/problem/1094