비트마스킹 (BitMasking)

rhkswls98·2023년 1월 2일
0
post-thumbnail

🛠️ 비트마스킹을 위한 선지식

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형 숫자의 한계까지만 가능합니다.
    그 이상은 경우의 수가 너무 커지므로 시간초과가 발생할 수 있습니다.

추천문제

백준 2098 외판원 순회
백준 1285 동전 뒤집기
백준 17471 게리맨더링

Reference

[큰돌의 터전 알고리즘 강의] 비트마스킹

profile
꺾이지 말자 :)

0개의 댓글