(C++) 비트와 부분 집합 (+ STL bitset 활용)

Date: 2021.04.01 Updated: 2021.04.01

카테고리: Algorithm

C++ Chapter 3.3 : 비트끼리의 연산, 비트 플래그, 비트 마스크

🚀 비트를 이용한 부분 집합

원소가 n개 인 집합이 있다고 할 때, n 자리의 비트를 사용하여 이 집합의 부분 집합을 표현할 수 있다. 👉 1 비트에 해당하는 자리만 활성화 한다고 생각하면 된다.

n개의 원소로 이루어진 집합이 있다고 할 때 부분 집합의 총 개수
- \(2^{n}\) 개
- 1 << n 개와도 같다.

{ A, B, C } 라는 집합이 있을 때 8 가지의 부분 집합을 구할 수 있다. 비트 값이 1 이면 그 비트에 대응되는 자리에 있는 원소가 부분 집합에 포함되어 있고, 비트 값이 0 이면 그 비트에 대응되는 자리에 있는 원소가 부분 집합에 포함되어 있지 않다고 생각해보면 된다.

0 👉 000 : { } 공집합
1 👉 001 : {A} 인덱스 0 에 해당하는 자리의 비트 값이 1 이므로
2 👉 010 : {B} 인덱스 1 에 해당하는 자리의 비트 값이 1 이므로
3 👉 011 : {A,B} 인덱스 0,1 에 해당하는 자리의 비트 값이 1 이므로
4 👉 100 : {C} 인덱스 2 에 해당하는 자리의 비트 값이 1 이므로
5 👉 101 : {A,C} 인덱스 0,2 에 해당하는 자리의 비트 값이 1 이므로
6 👉 110 : {B,C} 인덱스 1,2 에 해당하는 자리의 비트 값이 1 이므로
7 👉 111 : {A,B,C} 인덱스 0,1,2 에 해당하는 자리의 비트 값이 1 이므로

🔥 모든 부분 집합 구하기

void printSubsets(char arr[], int n) {
    for (int i = 0; i < (1 << n); ++i) {
        cout << "{ ";
        for (int j = 0; j < n; ++j) 
            if (i & (1 << j))
                cout << arr[j] << ",";
        cout << " }" << endl;
    }
}

int main(){
    char data[] = { 'A', 'B', 'C', 'D' };
    printSubsets(data, 4);
}

💎출력💎

{  }
{ A, }
{ B, }
{ A,B, }
{ C, }
{ A,C, }
{ B,C, }
{ A,B,C, }
{ D, }
{ A,D, }
{ B,D, }
{ A,B,D, }
{ C,D, }
{ A,C,D, }
{ B,C,D, }
{ A,B,C,D, }

🔥 두 원소의 합이 7이 되는 부분집합의 개수 구하기

int N, Arr[10];
int countBits(int i) {
    int count = 0;
    while (i) {
        if (i & 1) ++count;
        i = i >> 1;
    }
    return count;
}

int solve(int n, int arr[]) {
    int count = 0;
    for (int i = 0; i < (1 << n); ++i) {
        if (countBits(i) != 2) continue; // 원소가 2 개인 부분집합만 따질거라.. 즉, 1 비트의 개수가 2 개인 비트만 취급할 것

        int sum = 0;
        for (int j = 0; j < n; ++j) 
            if (i & 1 << j) // i 비트의 j 번째 자리가 1 인지 검사 (1이 맞다면 arr[j]은 부분집합에 포함할 원소)
                sum += arr[j];
        if (sum == 7) ++count;
    }
    return count;  
}

int main(){
    int n = 6;
    int arr[6] = { 1,2,3,4,5,6 };
    cout << solve(n, arr) << endl; // 3 을 출력할 것이다. {1, 6} {2, 5} {3, 4}
}

🔥 집합의 원소 개수

✈ STL 의 bitset 사용

    int n = 208;
    bitset<8> set = n; // n 을 8 bit 로 표현한 set 변수 (0 ~ 255 표현 가능)
    cout << set << endl;
    cout << set.count() << endl; // 원소의 개수나 마찬가지

💎출력💎

11010000
3

#include <bitset>

<bitset>의 count() 함수를 사용하면, 해당 변수에서 1 비트의 개수를 리턴해준다. 즉 이는 부분 집합의 원소 개수라고 대응시켜 생각해볼 수도 있다.

✈ 구현하기

    int n = 208;
    int count = 0;
    // 아래와 같은 방식으로 차례대로 각 자리마다 1 인지를 검사하며 된다.
    while (n) { // n 은 언젠가 0 이 됨
        if (n & 1) ++count; // 00000001 과 비교
        n = n >> 1; // 오른쪽으로 하나 씩 밀어서 없앰
    }
    cout << count << endl;

💎출력💎

3

🚀 정리

n개의 원소로 이루어진 집합이 있다고 할 때
- 부분 집합의 개수 👉 1 « n
- 원소가 있는지 확인하고 싶을 때 👉 i & (1 « j)
  - i 비트 안에 j 비트 자리가 1 인지 확인하고 싶을 때
  - 결과가 0 이 아니면 존재 하는 것
    - ex) 0101 & (1 « 2) = 0101 & 0100 = 0100 즉, 2번째 자리에 해당하는 비트가 1 인지를 확인할 수 있다.
- 원소를 추가하고 싶을 때 👉 i | (1 « j)
  - i 비트 안에 j 비트 자리를 1 로 만든다.
    - ex) 0101 | (1 « 1) = 0101 | 0010 = 0111 즉, 1번째 자리를 1 로 만들어줄 수 있었다.
- 원소를 삭제하고 싶을 때 👉 i & ~(1 « j)
  - i 비트 안에 j 비트 자리를 0 으로 만든다.
    - ex) 0101 & ~(1 « 2) = 0101 & ~0100 = 0101 & 1011 = 0001 즉, 2번째 자리를 0 으로 만들어줄 수 있었다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️