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

알고리즘

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

HSHyeon 2024. 10. 27. 23:00

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

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

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

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

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

비트마스킹이란?

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

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

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

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

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