비트셋으로 집합 표현하기 (Bitset)

 비트셋이란?

비트셋이란, 말 그대로 Set of Bits를 의미한다.

즉, 여러개의 비트가 모여서 하나의 집합을 형성하는 것 이다.

아래는 8비트를 나타내는 비트셋의 예시이며,

비트셋의 인덱스는 오른쪽에서 왼쪽으로 증가함에 유의하자.

 문제 제기

과일을 도메인으로 갖는 공간을 생각해보자.

아래의 집합은 서로 같은가? 다른가?

vector<과일> A = {사과, 포도, 딸기}

vector<과일> B = {사과, 딸기, 포도}

포도와 딸기의 위치가 바뀌긴 했지만,

그 집합의 구성원은 일치하므로 같은 집합이다.

하지만 벡터로 표현된 두 집합이 동치인지 확인하는 작업은

복잡하며, 벡터의 크기가 커질수록 느려진다.

 비트셋을 이용한 집합표현 (1)

비트셋은 정규화된 집합을 표현하는데 매우 효과적이다.

각 과일마다 비트의 인덱스를 하나씩 할당하고,

과일의 조합은 비트셋으로 표현하는 것 이다.

각 과일의 비트를 아래와 같이 설정하면,

사과 = 001

포도 = 010

딸기 = 100

Bitset of {사과, 포도, 딸기} = 111

Bitset of {사과, 딸기, 포도} = 111 이므로,

두 집합의 동치계산이 훨씬 쉬워진다.

 비트셋을 이용한 집합표현 (2)

도메인이 동적으로 결정되는 상황에서는

각 요소마다 비트를 어떻게 주면 될까?

vector<string> A = {"a", "Hello, World!", "b", "d", ...};
vector<string> B = {"Hello, World!", "b", "e", "a", ...};

힌트는 map<string, bitset>을 사용하는 것이다.

처음보는 문자열을 발견하면, bitset 인덱스를 동적으로 셋팅하자.

단, C++은 비트셋의 크기를 변경할 수 없으므로,

MAX_BIT_SIZE를 정해주어야 한다.

#include <bits/stdc++.h>
using namespace std;

//! 비트셋의 최대 크기.
const int MAX_BIT_SIZE = 8;
using bits = bitset<MAX_BIT_SIZE>;

//! 도메인.
map<string, bits> domain;

/**
 * 주어진 값에 연관되는 비트열을 가져온다.
 *
 * @param v 연관되는 비트열을 가져올 값.
 * @param strict 엄격모드 여부 : 도메인에 값이 없다면 예외발생.
 * @return 해당 값에 연관된 비트열.
 * 
 * @author https://aerocode.net
 */
bits get_elem_id(string &v, bool strict=false){
    if(domain.find(v) == domain.end()) {
        //! 엄격모드 : 도메인에 값이 없다면 예외발생.
        if(strict) throw exception();

        //! 엄격모드가 아니라면, 도메인에 새롭게 추가.
        bits this_bit;
        this_bit.set(domain.size());
        domain[v] = this_bit;
    }
    return domain[v];
}

int main(){
    vector<string> arr = {"a", "b", "c", "a"};
    for(string& str : arr){
        cout << get_elem_id(str) << '\n';
    }
    return 0;
}

 집합연산

비트셋은 비트연산이 가능한 자료구조이고,

비트연산을 통해 집합연산을 효율적으로 구현할 수 있다.

• 합집합 (Union)

합집합은 두 비트셋의 OR 연산으로 구현할 수 있다.

• 교집합 (Intersection)

교집합은 두 비트셋의 AND 연산으로 구현할 수 있다.

• 차집합 (Substraction)

차집합은 감수에 NOT을 취한 뒤, 피감수와 AND 시킴으로써 구현할 수 있다.

• 여집합 (Complement)

여집합은 한 비트셋에 NOT을 취함으로써 구현할 수 있다.

 비트셋의 강점

• 집합을 map의 K로 사용할 수 있다.

비트셋은 집합을 비트열로 표현하므로 정수로써 표현될 수 있으며,

연관자료구조의 KEY로써 효과적으로 작동한다.

• 집합연산을 빠르게 구현할 수 있다.

벡터로 집합연산을 구현하려면 2개의 for이 필요하지만.

비트셋으로 표현하면 1줄의 비트연산으로 끝난다.

즉, 성능과 생산성 둘 다 얻을 수 있다.

• bool[]보다 메모리를 적게 먹는다.

bool은 사실 1byte 자료형이다.

bitset은 각각의 칸이 1bit 이다.