🛠️ 비트마스킹을 위한 선지식
1. 이진수
- 간단하게 이진수란 0과 1로 이루어진 수를 말합니다.
1) 이진수를 이용해서 Boolean Array을 표현
- 비트마스킹에서 중요한 건 이 부분 입니다.
- 예를 들어 1 = 001(2) 은 0번째 비트가 켜져있다고 할 수 있습니다.
- 3 = 011(2) 은 0, 1번째 비트가 켜져있다고 할 수 있습니다.
즉, 이진수를 이용해서 하나의 숫자로 Boolean Array 을 표현할 수 있습니다.
처음 제가 비트마스킹 강의를 들었을 때 이랬습니다..
저도 그래서 다시 정리해봅니다..
아래 내용들을 다 보시면 어느정도 감이 잡히실겁니다.
2. 비트연산자
- (1 << n) : n 만큼 왼쪽으로 비트를 이동
- (1 >> n) : n 만큼 오른쪽으로 비트를 이동
1) n &= ~(1 << idx) : idx번째 비트 0 만들기
void bitmasking() {
int n = 15;
int idx = 0;
n &= ~(1 << idx);
cout << "idx번째 비트 0 만들기 : " << n << '\n';
//before 011011
//after 011010
}2) n ^= (1 << idx) : idx번째 비트 0은 1로, 1은 0으로
void bitmasking() {
int n = 5; //1001
int idx = 1;
n ^= (1 << idx);
cout << "idx번째 XOR 연산 : " << n << '\n';
//before 1001
//after 1011
}3) idx = (n & -n) : 켜져있는 최하위 비트 찾기
- 여기서는 -n 이 어떤건지 알아야합니다. n이 0010 일 때 ~n은 1101이 됩니다.
-n은 (~n + 1) = -n 의 특징을 가지므로 -n & n (1110 & 0010) 을 통해 켜져있는 비트 중 가장 아래에 있는 비트를 찾을 수 있게 됩니다.
void bitmasking() {
int n = 6;
int idx = (n & -n);
cout << "최하위 비트 찾기 : " << idx << '\n';
// 0110 1000
// idx = 2 idx = 8
}4) (1 << n) - 1 : 크기가 n인 집합의 모든 비트를 1로
void bitmasking() {
int n = 4;
cout << "크기가 n인 집합의 모든 비트 켜기 : " << (1 << n) - 1 << '\n';
// before 0100 = 4
// after 1111 = 15
}5) n |= (1 << idx) : idx번째 비트 1로 만들기
void bitmasking() {
int n = 8;
int idx = 2;
n |= (1 << idx);
cout << "idx번째 비트 1로 만들기 : " << n << '\n';
// before 1000 = 8
// after 1100 = 12
}6) if(n & (1 << idx)) : idx번째 비트가 1인지 확인
void bitmasking() {
int n = 15;
int idx = 0;
string s = n & (1 << idx) ? "yes" : "no";
cout << "idx번째 비트가 1인가? : " << s << '\n';
// 1111 = 15
// yes 출력
}🛠️ 비트마스킹이란?
-
예시로 저는 BFS/DFS 문제들에서 방문한 지역을
bool vst[1004]와 같은 Boolean 배열로 체크를 해주었습니다. -
반면, 비트마스킹은 Boolean 배열의 역할 을 하는 "하나의 숫자" 를 만들어서 "비트 연산자"를 통해 탐색, 수정 등의 작업 을 하는 것을 의미합니다.
1. 경우의 수 표현
-
비트마스킹으로 경우의 수를 표현할 수 있습니다.
-
예를들어 { "A", "B", "C", "D"} 를 조합하는 모든 경우의 수를 구해봅시다.
A
B
AB
ABC
....... 등등
4가지의 원소로는 16가지의 경우의 수가 나올 것 입니다.
#include<iostream>
using namespace std;
int main(){
int n = 4;
string s[n] = {"A", "B", "C", "D"};
for(int i = 0; i < (1 << n); i++){
string ret = "";
for(int j = 0; j < n; j++){
if(i & (1 << j)){
ret += s[j];
}
}
cout << ret << '\n';
}
return 0;
}
/*
A
B
AB
C
AC
BC
ABC
D
AD
BD
ABD
CD
ACD
BCD
ABCD
*/- i 의 값은 0000 ~ 1111 까지를 의미하고 j 의 값은 0 ~ 3 까지의 비트가 1인지를 확인하는 역할을 합니다. j 위치의 비트가 1이라면 ret에 추가해주었습니다.
2. 비트마스킹의 한계
- 비트마스킹은 31 까지만 가능합니다. 2^31
즉, int형 숫자의 한계까지만 가능합니다.
그 이상은 경우의 수가 너무 커지므로 시간초과가 발생할 수 있습니다.
추천문제
Reference
꺾이지 말자 :)