멱집합 (부분집합 - Power Set) 알고리즘
멱집합 알고리즘 멱집합은 한 집합의 모든 부분집합을 뜻합니다. 원소 a,b,c를 갖고 있는 집합의 모든 부분 집합은 (a, b, c, ab, ac, bc, abc + 공집합)으로 총 8가지 입니다. 탐색 (재귀, 브루트포스) 알고리즘 문제를 풀때 멱집합을 구하는 방법을 종종 사용하게 됩니다. 모든 부분집합의 경우의 수를 구하는 과정은 다음과 같습니다. 첫번째 원소가 포함이 되는가? 혹은 안되는가?→ 두번째 원소가 포함이 되는가? 혹은 안되는가? → . . . → N번째 원소가 포함이 되는가? 혹은 안되는가? 그래서 원소의 갯수가 N인 집합의 모든 부분집합의 갯수는 2^N개가 됩니다. 아래는 주어진 집합의 모든 부분집합을 출력하는 (java)코드입니다. 핵심부분은 위에서 설명한대로 n번째의 원소가 포함이 ..
Algorithm
2018. 12. 19. 21:12