[C++] 모든 부분집합을 출력하기

2017. 10. 4에 쓰여진 글입니다

---

 

모든 부분집합을 출력하기

#include <iostream>
 
using namespace std;
 
int main()
{
    int i, j;
    int arr[3] = { 1,2,3 };
    int n = sizeof(arr)/sizeof(arr[0]);
 
    for (int i = 0; i < (1 << n); i++) {    // 1<<n은 2^n 따라서 부분집합의 개수
        for (int j = 0; j < n; j++)    //원소의 개수만큼 for문 돌아감
            if (i&(1 << j))        //i&(1<<j) i의 j번째 bit가 1인지 아닌지를 확인함
                cout << arr[j] << " ";
        cout << endl;
    }
    
    return 0;
}

모든 부분집합 출력

 

왜 부분집합이 위의 그림과 같은 순서로 출력될까요?

이건 2진수를 표현하는 방법에 있습니다.

위의 예시로 해보면

for (int i = 0; i < (1 << 3); i++)

첫번째 for문은 이렇게 되어있습니다. 즉 0~7까지 8번돌리겠다는 의미죠.

그럼 각각 i값의 10진수표현과 2진수 표현을 써보면

10진수 2진수

0      0000

1      0001

2      0010

3      0011

4      0100

5      0101

6      0110

7      0111

이렇게 되죠.

눈치 채셨나요?

위의 예시에서 각각의 배열의 원소를 출력한다고 했죠. 

 

2진수에서 각각 1인부분만 출력이 된걸 보실수가 있습니다.

그럼 왜 그럴까요? 

if (i&(1 << j))

이 문장을 보시면 & (AND) 연산자를 쓴걸 볼수있습니다.

만약 i가 6라고 해보면

0110 이겠죠? 그럼 j는 0~3까지 1<<j를 해줍니다. 즉

j=0일때        j=1일때       j=2일때

   0110         0110          0110

& 0001       & 0010        & 0100

-----------------------------------

   0000         0010          0100

 

이렇게 나오겠죠. if(0이아닌 숫자) 를 만족하면 arr[j]를 출력해줄꺼니까

i=6일경우에는 arr[1], arr[2]가 출력되겠죠.

그래서 위의 부분집합 출력사진에서 6번째가 2와 3이 나온겁니다. 이해 되셨나요? 

즉 & 연산을 해서 어떤 숫자가 나오면 해당 번째 2진수가 있는거니까 출력해주겠다 이말입니다.

비트마스킹에 대해서 좀더 궁금하다면 해당 포스팅 참조.

 

https://royhelen.tistory.com/30

[C++] 비트마스킹, 비트마스크, 비트연산자