완전탐색 - 비트마스크 기초

완전 탐색 - 비트마스크

비트 연산

shift left (<<) , shift right (>>) 두개의 연산이 있다

A >> B (A 를 오른쪽으로 B비트만큼 이동)

1 >> 1 0(이진법)

10 >> 1 101(이진법)

10 >> 2 1010 을 오른쪽으로 2비트 이동 ==> 10 즉 2가 됨

 

A << B 는 A * 2^B

A >> B 는 A / 2^B

 

이것을 이용하여 할 수 있는 것은 정수를 통해 집합을 표현할 수 있다.

만약 10명의 학생이 있고, 0~9번 이라는 번호로 학생을 표현하고 싶을 때 1,3,5,7,9 번의 학생을 한 집합으로 표현한다면,

$$2^1 + 2^3 + 2^5 + 2^7 + 2^9 = 682$$

이런 식으로 표현이 가능하며, 2진법으로 표현한다면 1010101010(2) 으로 표현할 수 있다.

만약에 내가 5번 학생이 있는걸 확인하고 싶으면

 
xxxxxxxxxx
int sum = 682;
if(sum & (1 << 5)) cout << "5번 학생이 있다" << '\n';

이 집합 상태에서 어느 한 학생을 추가(삽입) 하고싶다면 OR(|) 연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum | (1 << 2);   // 2번 학생을 추가

$$682 | 2^2 = 682 |(1 << 2) = 686 (1010101110(2))$$

여기서 + 연산을 사용하지 않은 이유는 carry가 발생하여, 다른 값에 영향을 줄수 있기 때문에 OR연산을 사용한다.

 

집합에서 어느 한 학생을 제거(삭제) 하고 싶다면 N0T(&)연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum & ~(1 << 5);  // 5번 학생을 제거

 

전체 집합 표현

$$(1 << N) - 1 = 2^N - 1$$

공집합

$$0$$

 

A라는 집합에서 특정 n 을 추가 할때

A | (1 << n)

A라는 집합에서 특정 n 을 확인 할때

A & (1 << n)

A라는 집합에서 특정 n 을 제거 할때

A & ~(1 << n)

A라는 집합에서 각 값을 토글 할때

A ^ (1 << n)

 

비트마스크 연산 연습해보기

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

소스 코드

 
x
#include<iostream>
#include<string>
using namespace std;
​
int sum;
​
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string ins;
        cin >> ins;
        if(ins == "add")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum | (1 << tmp);
        }
        else if(ins == "remove")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum & ~(1 << tmp);
        }
        else if(ins == "check")
        {
            int tmp;
            cin >> tmp;
            if(sum & (1 << tmp)) cout << "1" << '\n';
            else cout << "0" << '\n';
        }
        else if(ins == "toggle")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum ^ (1 << tmp);
        }
        else if(ins == "all")
            sum = (1 << 20) - 1;
        else if(ins == "empty")
            sum = 0;
    }
    return 0;
}