[Algorithm] 비트마스크 (Bit-mask) #230210

비트마스크(bitmask) 란 ?

이진수 표현을 자료구조로 쓰는 기법이다.

 

비트 연산자

• a & b : AND 연산
• a | b : OR 연산
• a ^ b : XOR 연산
• ~a : NOT 연산
• a << b : 정수 a를 왼쪽으로 b비트 Shift
• a >> b 정수 a를 오른쪽으로 b비트 Shift

비교 연산자 → 비트 연산자의 우선순위

 

집합의 구현

int noPizza = 0; // 공집합
int fullPizza = (1 << 20) - 1; // 꽉찬 피자

0부터 19까지의 번호를 가진 토핑을 가진 피자집이 있다.

20개의 토핑을 모두 올린 피자는 아래와 같이 표현할 수 있는데, 20개의 0을 가진 비트를 만들고 1을 뺴면 20개의 비트가 모두 켜진 수를 얻을 수 있다.

p번째 있는 토핑을 추가하고 싶으면, 현재 토핑 목록인 toppings에 p비트만 켜진 정수를 비트별 OR 처리하면 된다

toppings |= (1 << p); 

 

원소 포함 여부 확인

if(toppings & (1 << p)) cout << "페퍼로니 있다!" << endl;

위의 연산을 이용해서, toppings에 p가 있는지 확인하려면 & 연산자를 사용하면 된다.

이 if문의 연산 결과는 0 혹은 1<<p이다.

 

원소의 삭제

toppings -= (1 << p);

토핑이 없는 경우에 정상적으로 동작하도록 원소를 삭제하기 위해서는

toppings &= ~(1 << p); 

이렇게 하면 페퍼로니가 없는 경우에도 (0) AND 연산자를 적용하게 되어 동일하게 0이 된다.

 

원소의 토글

toppings ^= (1 << p); 

페퍼로니가 있으면 (1) XOR 연산을 통해 0이 되고, 없으면 (0) 1이 된다.

 

집합의 크기 구하기

int bitCount(int x){
    if(x == 0) return 0;
    return x % 2 + bitCount(x/2);
}

모든 비트를 순회하면서 켜져 있는 비트의 개수를 세는 프로그램이다.

현재 비트에서 켜져있는 최하위 비트를 구하기 위해 아래 로직을 사용한다.

int firstTopping = (toppings & -toppings); 

음수를 표현할 때 2의 보수를 취하는데, 이 원리를 사용해서 toppings와 -toppings를 AND한 결괏값은 항상 켜져있는 최하위 비트를 도출한다.

 

최소 원소 지우기

toppings &= (toppings - 1);

특정 비트값에서 1을 뺀 값과 원래 비트값을 AND 연산하면 최하위에 켜져있는 비트가 꺼진다.

 

모든 부분집합 순회하기

for(int subset = pizza; subset; subset = ((subset -1) & pizza) {
    // subset은 pizza의 부분집합
}

(subset -1) & pizza 를 통해 최하위 비트가 꺼진 subset과 pizza가 AND 연산을 수행하여 pizza와 겹쳐지는 부분만 subset에 남게 된다. 이 연산을 반복하면 pizza의 모든 부분집합을 방문할 수 있다.

극대 안정 집합

#include <iostream>
#include <vector>
#define MAXN 100
using namespace std;

int n;
int explodes[MAXN]; // i 물질과 같이 두었을 때 폭발하는 물질 집합의 비트마스크

bool isStable(int set) { 
    for (int i = 0; i < n; i++) {
        // i 물질이 현재 탐색하고 있는 물질 집합에 포함되어 있으면
        // 폭발하는 물질이라면
        if ((set & (1 << i)) && (set & explodes[i])) 
            return false; 
        return true;
    }
}

// 모든 극대 안정 집합의 개수를 센다 (하나라도 물질을 더 넣으면 폭발)
int countStableSet() {
    int ret = 0;
    for (int set = 1; set < (1 << n); set++) { // (1 << n)은 n개의 모든 물질 집합의 비트마스크를 나타냄.
        if (!isStable(set)) continue;  

        bool canExtend = false; // 더 넣을 수 있는가?
        for (int add = 0; add < n; add++) {
            // 현재 물질 집합에 add가 포함되어 있지 않고 (같은 물질은 예외로 둔다)
            // 현재 물질에 add를 넣으면 explodes하지 않는 경우 (=> 더 넣을 수 있다!) 
            if ((set & (1 << add)) == 0 && (explodes[add] & set) == 0) {
                canExtend = true;
                break;
            }
            if (!canExtend) // 더 넣을 수 없다면 극대 안정 집합의 개수를 늘린다.
                ret++; 
        }
        return ret; 
    }
}

 

문제 : 졸업학기

각 한기를 한 조각으로 쪼개서 계산한다.

graduate(semester, taken)

:  현재 학기가 semester이고, 지금까지 들은 과목이 taken일 때, 앞으로 다녀야하는 최소 학기의 수

이라고 가정하면, 선수 과목을 모두 들은 과목들 중 L개 이하를 선택하고, 이 선택의 조합들을 모두 테스트하는 함수 choose()를 만든다고 하자.

하나의 학기에서 choose()를 호출하고 모든 경우의 수를 계산하기 위해 choose()를 재귀호출 후 L개를 모두 선택하면 graduate()를 호출하는 구조가 된다. ⇒ 너무 복잡하므로 비트마스크를 사용 !

 

비트마스크 적용 영역

 

(1) taken과 prerequisite[i]의 교집합이 prerequisite[i]와 동일한지 확인
⇒ 인자로 가져오는 아이와 기존에 매칭해놓은 게 같은지 비교
(2) 이번학기에 들을 수 있는 과목만을 넣은 canTake를 구현하기 위해, 들을 수 있는 전체 과목에서 선수과목을 다 듣지 않아 들을 수 없는 과목을 제외한다.
(3) 이미 들은 과목의 수 + 이번 학기에 들을 과목의 수 계산하는 bitCount()

#include <iostream>
#include <vector>
using namespace std;
#define MAXN 13 // 전공 과목의 최대 수
#define MAXM 11 // 학기의 최대 수

int n, k, m, l;

const int INF = 987654321;
int prerequisite[MAXN];

int classes[10];  // i 학기에 개설되는 과목의 집합
int cache[10][1 << MAXN];

int bitCount(int n);

int graduate(int semester, int taken) {
    // 기저사례 1 : 수강한 과목이 k개가 넘으면 종료
    if (bitCount(taken) >= k) return 0;

    // 기저사례 : 학기가 m과 같아지면 종료
    if (semester == m) return INF;

    // 메모이제이션
    int& ret = cache[semester][taken];
    if (ret != -1) return ret;

    ret = INF;
    int canTake = (classes[semester] & ~taken); // 듣지 않은 것 중에 이번 학기에 열리는 강의를 담는다. 

    // 모든 강의를 순회
    for (int i = 0; i < n; i++) {
        // 해당 강의가 수강 가능하고
        // 선수강 조건을 충족하지 않은 경우에
        if ((canTake & (1 << i)) && (taken & prerequisite[i]) != prerequisite[i])
            canTake &= ~(1 << i); // 수강 가능 목록에서 제외
    }

    // canTake의 모든 부분집합을 순회한다. 
    for (int take = canTake; take > 0; take = ((take - 1) & canTake)) {
        if (bitCount(take) > l) continue; // 학기 당 들을 수 있는 과목의 수를 초과한 경우

        // 현재 ret 값과, 
        // 이번 학기에서 들은 take를 taken에 더해주어 다음 학기로 넘겨주면서 재귀호출한 값과, 비교해서 최솟값을 구해줌
        ret = min(ret, graduate(semester + 1, taken | take) + 1);
    }
    ret = min(ret, graduate(semester + 1, taken));
    return ret;
}

이 코드의 전체적인 로직(1) canTake , 현재학기에서 수강 가능한 목록을 구한다.
(2) 비트마스크를 이용해서 canTake의 모든 집합을 순회하며, 재귀호출하여 최솟값을 구해준다.