Bitset은 int를 대체할 수 있을까?

2023. 12. 20. 01:34

최근 알고리즘 공부에 푹 빠져지내고 있다. 예전에는 문제유형을 분석하는 연습을 많이 했다면 요즘에는 한 유형을 깊게 공부하는 재미에 들었다. 

대부분의 알고리즘 강의에서 비스마스킹을 int로 푸는 방법을 설명한다. int로 비트연산자 사용이 가능하지만 나는 bitset의 존재를 알고 있었다. bitset을 공부한다면 문제풀이에 도움이 되지 않을까하는 생각이 들었다. 오늘은 bitset에 대해 알아보자

 

bitset 사용방법

- 비트셋(Bitset)이용 방법 및 선언

 

#include <bitset>를 이용

bitset<개수> 이름;:: bitset 선언

 

- 비트셋(Bitset) 함수

 

bit.set() :: 전체 비트를 1로 셋팅

 

bit.set(n, true/false) :: n+1번째 비트를 1또는 0으로 셋팅

bit.reset() :: 전체 비트를 0으로 리셋

 

bit.size() :: bitset의 크기를 구한다.

 

bit.any() :: 비트셋 중 하나라도 1이면 1을 반환, 모두 0일때만 0을 반환

 

bit.none() :: 비트셋 중 모두가 0이어야 1을 반환

 

bit.flip() :: 전체 비트를 반전

 

bit.flip(n) :: n+1번째 비트를 반전

 

bit.test(n) :: n+1번째 비트를 검사(1인지 0인지)

 

bit.to_string() :: 전체 비트를 string화 시킨다.

 

bit.to_ulong() / bit.to_ullong() :: 전체 비트를 unsigned long / unsigned long long 의 값으로 바꿔준다.

 

bit.test[4] == bit[4] :: 배열처럼 이용이 가능하다.

 

문제로 알아보자

비스마스킹의 대표적인 문제로 외판원 순회 문제를 풀어보았다. 코드를 읽어보면서 int로 풀었을 때와 무엇이 다른지 확인해 보자.

 

int dfs(int cur, bitset<20> visited) {
    if(biton(visited)) { // 1️⃣
        if( adj[cur][0].second == 0 ) return adj[cur][0].first;
        else return inf;
    }
    
    if(dp[cur][visited.to_ulong()] != -1) return dp[cur][visited.to_ulong()];
    dp[cur][visited.to_ulong()] = inf; // 2️⃣
    
    for(auto [cost, there]: adj[cur]) {
        if(visited.test(there)) { continue; } // 3️⃣
        
        auto newbit = bitset<20>(visited); // 4️⃣
        newbit.set(there, 1);
        dp[cur][visited.to_ulong()] = min(dp[cur][visited.to_ulong()],
                                          cost + dfs(there, newbit));
    }
    
    return dp[cur][visited.to_ulong()];
}

 

1️⃣ 모든 비트가 켜져있는지 확인하기 위해 .all() 함수를 호출할 수 있지만, 실질적으로 코딩테스트에서 사용하기 어렵다.

문제에서 n을 입력으로 주어지기 때문에 변수를 선언할 때 충분한 크기를 가진 bitset으로 초기화한다. 그럼 사용하지 않는 bit는 무조건 0이 되기 때문에 all()함수가 의미가 없다. 

모든 비트가 켜져있는지 확인하기 위해서, biton(bitset<20>& bits) 라는 함수를 만들어줘야만 했다.

 

bool biton(bitset<20>& bits) {
    for(int i=0; i<n; i++){
        if(bits[i] == 0) return false;
    }

    return true;
}

 

cin >> n;
auto bit = bitset<n>(); // error!!

 

2️⃣ 비트마스킹를 인덱스로 사용할 때 to_ulong() 함수를 사용해야 한다. 함수이름이 길어서 개인적으로 보기 좋다고 생각하지 않는다. 그리고to_int() 함수도 없다는게 아쉽다.

 

3️⃣ pos번째 비트가 켜져있는지 확인하는 코드가 깔끔하다. int를 사용한다면 아래코드처럼 작성해야하지만 test()함수를 사용이 간편하다.

(visited & 1 << there) == 1 << there
// << 연산자가 &보다 우선순위가 높다.
// == 연산자가 &보다 우선순위가 높아서 괄호를 꼭 넣어줘야한다.

 

4️⃣  bitset의 함수의 반환은 참조값을 가집니다. 변수를 초기화할 때 얕은복사만 일어납니다. dfs의 알규먼트에 값을 전달해야하는데, 새로운 변수를 선언해야만 합니다.

$clangPATH/inclue/bitset/bitset.cpp

 

결론

bitset의 test(), operator[]() 함수는 코드를 간소화시킬 수 있어서 매력적이다. 하지만 그 외 다른 모든 함수의 사용이 불편하다. 코딩테스트 공부를 할때 bitset보다 int가 더 적합하다.

티스토리툴바