비트마스킹 (백준 11723번 집합)

 

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

11723번: 집합

 문제에서 비트마스킹을 처음 접했다. 비트마스킹을 이용해 집합을 표현하고 원소에 접근하면 접근 시간 복잡도가 O(1)로 짧게 걸리고 메모리도 사용량이 적다는것이다. 이번 문제에서는 메모리 사용량이 제한되어있고 이는 비트마스킹 기법을 이용해야지 이 메모리 조건을 통과 할 수 있는 것이었다. 

 

비트마스크(Bit Mask)

- 정수의 이진수 표현을 자료 구조로 사용하는 기법이다. 예를들어 4라는 숫자는 0100으로 표현이 가능하다. C++에서 int형 자료형은 4바이트를 사용한다. 즉 1byte = 8bit 이기때문에 32비트까지 숫자 표현이 가능하다. 이를 이용해 32개의 원소를 가진 집합도 표현 할 수 있다.

 

- 비트에서 '1'이면 켜져있다고 표현하고, '0'이면 꺼져있다고 표현한다.

 

장점

1)수행 시간이 빠르다.

다른 자료구조와 다르게 Bit연산으로 모든걸 해결하기 때문에 접근시간이 대부분 O(1)인 경우가 많다. 당연하겠지만 연산 횟수가 많아질수록 비트마스킹 기법이 유리하다.

 

2)메모리 사용량이 적다.

아까처럼 int자료형을 예를들면 사실상 메모리는 4byte밖에 쓰지않는다. 하지만 비트마스킹 기법에서 우리가 표현할 수 있는 숫자는 2의 32제곱 만큼을 표현할 수 있다. 매우 많은 데이터들을 적은 메모리를 사용하며 저장할 수 있다.

 

연산

기본적으로 비트이기 때문에 모든 비트 연산이 가능하다. 이를통해 비트마스크 기법으로 집합을 만들었을때 비트 연산으로 원소 삽입, 제거, 체크, 반전 등 많은 작업들이 가능하다.

 

int a,b;

 

1. 시프트 연산 

a<<n (a의 이진수형태의 모든 비트를 n번 왼쪽으로 shift) 

a>>n (a의 이진수형태의 모든 비트를 n번 오른쪽으로 shift)

shift후 남은 뒤에 칸은 0으로 채움

2. OR 연산

a|b 하나라도 1이면 1이고, 둘다 0인 경우만 0

3. AND 연산

a&b 하나라도 0이면 0이고, 둘다 1인 경우만 1

4. XOR 연산

a^b 서로 다른 비트일 경우에만 1이고, 둘다 같은 비트일 경우는 0

5. NOT 연산

~a 모든 비트의 반전

 

비트마스킹을 통한 집합 표현

비트의 자릿수를 집합의 원소라고 생각한다.

ex) 1001이라는 집합이 있다고하면 index 0의 원소가 존재, index 3원소 존재 0비트는 해당 인덱스의 원소가 존재하지 않는다고 표현한다.

 

따라서 우리는 비트마스킹의 연산을 통해 집합의 연산을 수행 할 수 있다.

 

int s = 0; //공집합 s 선언, 초기화를 꼭 해주어야함

int형 자료형으로 s를 선언하였기 때문에 s는 0000 0000 0000 0000 0000 0000 0000 0000 32개의 비트를 가진다.

s = s|(1<<n); // n 원소 추가

1을 n만큼 왼쪽 shift후 s와 or연산을 하면 s집합에 n번째 인덱스에 1이 추가된다.

s = s&~(1<<n);

n만큼 왼쪽 shift후 not연산을 통해 n번째 인덱스만 0으로 만들고 s와 and연산을하면 s집합의 n번째 원소를 제거한다.

s&(1<<n); //n번째 원소가 존재하는지 확인

n번 왼쪽 shift후 s집합과 and연산을해서 옳으면(원소가 존재) True를 반환 옳지 않으면 (원소가 존재하지 않음) False를 반환한다.

s ^= (1<<n); //n번째 비트 반전

XOR연산을 통해 원소가 존재하면 n을 제거하고, 존재하지 않으면 원소 n을 추가하는 집합 연산을 할 수 있다.

s = (1<<n+1)-1; //n비트까지 1로 채움

n+1만큼 왼쪽 shift후 1을 빼주면 맨 상위 비트 (n+1)은 제거되고 그 하위비트들은 모두 1로 바뀐다. 즉 n번 인덱스까지 모든 원소를 채우는 집합 연산을 해줄 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int a=0;
    int n;

    cin>>n;
    int num;

    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;

        if(str=="add")
        {
            cin>>num;
            a = a|(1<<num);
        }
        else if(str =="check")
        {
            cin>>num;
            if(a&(1<<num))
                cout<<1<<'\n';
            else
                cout<<0<<'\n';
        }
        else if(str =="remove")
        {
            cin>>num;
            a &= ~(1<<num);
        }
        else if(str == "toggle")
        {
            cin>>num;
            a^= (1<<num);
        }
        else if(str == "all")
        {
            a = (1<<21)-1;
        }
        else if(str == "empty")
            a = 0;
    }
    return 0;
}

위 연산을 기반으로 백준 집합문제를 해결한 코드이다.