jasonbla

[Algorithm] 부분 집합(power set) 본문

Programming

[Algorithm] 부분 집합(power set)

jason jason hwang 2016.10.26 00:53

본 글은 아래 블로그에서 참고하여 작성한 글임을 먼저 밝힙니다.


http://dumpsys.blogspot.kr/2015/03/algorithm-binary-counting-power-set.html

http://hochulshin.com/permutation-composition-summary/

http://swlock.blogspot.kr/2016/03/power-set.html


알고리즘 문제를 풀면서 항상 막히는 부분에 대한 정리가 필요하여 다른 블로그를 참고해 요약을 해보았다. 

앞서 정리했던 순열 조합 알고리즘과 마찬가지로 문제를 풀다보면 다음과 같이 N개의 숫자로 이루어진 집합에서 부분 집합(Power set)을 구해야 하는 경우가 종종 발생한다.


ㅁ 4개의 숫자


1, 2, 3, 4 


ㅁ 4개의 숫자로 만들어 낼 수 있는 부분 집합(Power set)


2진수 | 원소

0001  | 1

0010  | 2

0011  | 1, 2

0100  | 3

0101  | 1, 3

0110  | 2, 3

0111  | 1, 2, 3

1000  | 4

....(생략)....

1111  | 1, 2, 3 ,4


각 집합은 중복되지 않는 유일한(Unique) 원소의 조합이므로 비트 연산을 통해 부분 집합을 구할 수 있다. 


ㅁ 4개의 숫자(4Bit)로 만들어 낼 수 있는 부분 집합의 수


2^4 = 16개


16개의 부분 집합이 만들어지는데 각 비트가 1이 되는 자리의 원소를 출력해주면 된다. 


C++ 코드



0 Comments
댓글쓰기 폼