🔧변경내용🔨

제목	날짜	내용
발행일	23.04.05

📌들어가기에 앞서

해당 포스트는 멱집합를 학습한 것을 정리한 내용입니다.

---

🌈 멱집합

집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개다.

그리고 이 모든 부분집합을 통틀어 멱집합이라고 한다.

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

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

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

• Step A: 1을 제외한 {2, 3}의 부분집합을 나열

  • Step B: 2를 제외한 {3}의 부분집합을 나열

    • Step C: 3을 제외한 {}의 부분집합을 나열 → {}

    • Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열 → {3}

  • Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열

    • Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면,

      {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음

      {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열 → {2}, {2, 3}

• Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열

  • Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면,

    {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음

    {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열

    • Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면,

      {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음

      {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열. → {1}, {1, 3}

    • Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면,

      {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음

      {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열 → {1, 2}, {1, 2, 3}

원소가 있는지, 없는지 2가지 경우를 고려하기 때문에 집합의 요소가 n 개일 때 모든 부분집합의 개수는 2n개다.

예를 들어 집합의 원소가 4개라면 모든 부분집합의 개수는 24, 집합의 원소가 5개라면 25가 된다.

간단히 {1, 2, 3}의 모든 부분집합을 구하는 단계는 다소 복잡해 보일 수 있다.

이 단계를 자세히 보면, 어디서 많이 본 듯한 패턴이 보인다.

이 순서는, 트리구조와 비슷한 형태를 가지고 있다.

멱집합 문제는 트리 문제가 아니다. 그림은 이해를 돕기 위해 사용되었다.

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

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

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

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

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

---

Power Set

집합 S가 있을 때, Power Set인 P(S)는 집합 S의 거듭제곱 집합으로, S의 모든 부분 집합의 집합을 의미한다.

예를 들어 S가 {a, b, c} 으로 요소가 3개일 때,

P(S)는 {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}} 으로 요소가 8개임을 알 수 있다.

즉 S에 n개의 요소가 있다면 P(S)에는 2n의 요소가 있음을 의미한다.

Example

Set = [a, b, c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter        Subset
     000               Empty set
     001                   a
     010                   b
     011                   ab
     100                   c
     101                   ac
     110                   bc
     111                   abc

이제 알고리즘 로직을 보도록 하자.

Input : Set[], set_size

1. 모든 집합의 크기를 가져온다. power_set_size = pow(2, set_size)

2. 0에서부터 power_set_size까지의 반복문 실행

   a. i = 0에서 set_size까지 크기를 지정해 반복문을 실행.
   그리고 집합에서 i번째 요소에 해당하는 하위 집합을 출력

   b. 하위 집합을 구하면 개행을 통해 집합을 구분

주어진 집합 S에 대해 거듭제곱 집합은 0과 2n-1 사이의 모든 이진수를 생성하여 찾을 수 있다.

여기서 n은 집합의 크기다.

예를 들어 집합 S {x, y, z}에 대해 0부터 23-1까지의 모든 이진수를 생성하고, 생성된 각 숫자에대해 해당 숫자의 집합 비트를 고려하여 해당 집합을 찾을 수 있다.

아래는 위에서 소개한 접근 방식을 구현한 것이다.

let inputSet = ['a', 'b', 'c'];

function powerSet (arr) {
	const result = [];
	function recursion (subset, start) {
		result.push(subset);
		for(let i = start; i < arr.length; i++){
			recursion([...subset, arr[i]], i+1);
			//이렇게도 구현할 수 있다.
			//recursion(subset.concat(arr[i]), i+1);
		}
	}
	recursion([], 0);
	return result;
}
powerSet(inputSet);

Output

[
  [],
  [ 'a' ],
  [ 'a', 'b' ],
  [ 'a', 'b', 'c' ],
  [ 'a', 'c' ],
  [ 'b' ],
  [ 'b', 'c' ],
  [ 'c' ]
]

위의 powerSet 로직은 재귀함수를 이용하여 구현한 것이다.

재귀함수에 부분집합을 만들기 위한 빈배열과 시작할 숫자를 지정한다.

이어 숫자가 커지게끔 하면서 중심 로직인 반복문을 돌려 부분집합을 만든 뒤, 최종적으로 배열 result에 push한다.

---

📚 레퍼런스