-
[Algorithm] 부분 집합(power set)Programming 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++ 코드
int main(void) { char arr[MAX] = { '1', '2', '3', '4' }; /* 원소의 길이만큼 오른쪽으로 Shift 연산 Before : 0000 0001 After : 0001 0000 ==> 16 */ for (int i = 1; i < (1 << MAX); i++) { for (int j = 0; j < MAX; j++) { /* AND 연산을 통해 검사할 비트의 자리가 1인 경우에만 해당 원소를 출력 e.g. i == 1, j == 0 0001 (i) 0001 (1<<0) 0001, arr[0] 출력 i == 1, j == 1 0001 (i) 0010 (1<<1) 0000, 출력X */ if (i & (1 << j)) { cout << arr[j] << ", "; } } cout << endl; } return 0; }
'Programming' 카테고리의 다른 글
[Android] 피카소(Picasso) 라이브러리 소개 및 주의할 점 (0) 2017.09.23 [Android] Asset Studio 활용하여 해상도별 Launcher Icon 세팅하기 (0) 2017.01.08 [Android] Play Store 업데이트, zipalign 사용법 (1) 2016.12.12 [Algorithm] 순열 조합 (0) 2016.10.23