(Advanced) Algorithm with Math - 멱집합

(Advanced) Algorithm with Math - 멱집합

어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합 이라고 합니다.

집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개입니다. 그리고 이 모든 부분집합을 통틀어 멱집합이라고 합니다.

 

이렇게  모든 부분집합을 나열하는 방법은 다음과 같이 몇 단계로 구분할 수 있습니다.

부분집합을 나열하는 방법에서 가장 앞 원소가 있는지, 없는지에 따라 단계를 나누는 기준을 결정합니다.

멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 확인할 수 있습니다.

여기서 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법입니다.

따라서, 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있습니다.

 

예를 들어 PowerSet 이라는 멱집합의 개수를 리턴하는 함수를 작성한다면, PowerSet 함수에서 자기 자신을 호출하며 문제를 더 작은 문제로 문제의 크기를 줄여 해결할 수 있습니다.

 

문제가 가장 작은 단위로 줄어들고, 함수가 리턴될 때 카운트를 올리는 방식으로 멱집합의 개수를 구할 수 있습니다.