Bit 연산으로 집합구하기

완전탐색을 하기 위해서는 여러 방법이 있을 수 있겠지만 

만약 int arr[] = { 1, 2, 3, 4 }; 라는 배열이 있다고 할 때,

이 부분 집합들을 구해야 한다면 어떻게 해야 될까요?? 

 

부분집합 크기가 1인 경우, 2인 경우 .. 4인경우 다 나눠서 구할 수는 있지만 

만약 arr의 크기가 100이라면? 그보다 크다면?!! 

딱히 생각나지 않습니다.. 이때! bit 연산으로 쉽게 구할 수 있습니다!

 

0000

0001

0010 ... 

 

이런식으로 각 결과마다 1인 부분만 출력한다면 쉽게 부분집합을 구할수 있겠죠??

먼저 코드를 보여드리고 설명하도록 하겠습니다. 

#include <iostream>
using namespace std;
int main() {
    // 배열 크기
    int n = 5;
    // 11111을 10진수로 환산 했을 때의 값만큼 반복 
    // (이 경우 0 ~ 31)
    for (int i = 0; i < (1 << n); i++) {
        // 자리수만큼(이 경우 5) 반복하며 
        // 1인 자리는 1을, 아니면 0을 출력
        for (int j = 0; j < n; j++) {
            if (i & (1 << j))
                cout << 1 << ' ';
            else
                cout << 0 << ' ';
        }
        cout << endl;
    }
    system("pause");
    return 0;
}

먼저, 첫 번째 for문을 보면, (1 << n) 부분이 있습니다. 1을 n번만큼 왼쪽으로 옮긴다는 소리로,

1은 00001이니, 이를 5번 옮기면 100000가 되겠죠? 10진수로 보면 32! 

즉, 2^5입니다. 그냥 pow(2, n) 으로 해도 상관 없겠지만 bit에 익숙해지는게 낫겠죠??

 

다음은 각 자리수 별로 체크하는 부분입니다. 

여기에서 &는 둘다 1이어야 1을 반환하는 연산자입니다.

i가 5일 경우를 보면 ( 00101 ),

j == 0일때, (1 << 0)은 1이 한칸도 안움직였으니 그대로 1입니다. 

   00101 & 00001 = 00001 = 1 => true

   그래서 1을 출력하겠죠?

j == 1일때, (1 << 1)

   00101 & 00010 = 00000 = 0 => false

j == 2 일때, (1 << 2)

   00101 & 00100 = 00100 = 4 => true

이후에는 다 0이므로 false 입니다.

 

이렇듯 안에 있는 두번째 for문은 1이 있다면 true 아니면 false로 처리하여 부분집합을 구하는 것입니다.

 

적절한 완전탐색 문제가 있다면 활용하면 좋겠네요!

 

질문이나 지적사항은 댓글로 부탁드립니다 :)

 

참고) https://www.crocus.co.kr/1427