멱집합(Power Set)이란?
집합 S의 멱집합(power set)은 S의 모든 부분집합을 원소로 가지는 집합으로, 공집합과 S 자기 자신까지 포함됩니다. 집합 S의 멱집합은 일반적으로 P(S)로 표기합니다.
예시
S = {x, y, z}일 때, 만들 수 있는 모든 부분집합은 다음과 같습니다.
{
{},
{x},
{y},
{z},
{x, y},
{x, z},
{y, z},
{x, y, z}
}원소가 n개인 집합의 멱집합은 항상 2ⁿ개의 부분집합을 가진다는 점을 기억하면 좋습니다. 위 예시에서도 원소가 3개이므로 2³ = 8개의 부분집합이 존재합니다.
문제 정의
배열을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 입력 배열의 멱집합을 계산하여 배열 형태로 반환해야 합니다.
구현 예제
다음은 비트마스킹(bitmasking) 기법을 활용한 코드입니다.
const set = ['x', 'y', 'z'];
const powerSet = (arr = []) => {
const res = [];
const { length } = arr;
const numberOfCombinations = 2 ** length;
for (let combinationIndex = 0; combinationIndex < numberOfCombinations; combinationIndex += 1) {
const subSet = [];
for (let setElementIndex = 0; setElementIndex < arr.length;
setElementIndex += 1) {
if (combinationIndex & (1 << setElementIndex)) {
subSet.push(arr[setElementIndex]);
};
};
res.push(subSet);
};
return res;
};
console.log(powerSet(set));
동작 원리
이 코드의 핵심은 비트 연산입니다. 0부터 2ⁿ−1까지의 각 숫자를 이진수로 표현하면, 각 비트가 해당 위치의 원소를 부분집합에 포함할지 여부를 나타냅니다.
- 예를 들어 combinationIndex가 5(이진수 101)라면, 첫 번째와 세 번째 비트가 1이므로 {x, z}라는 부분집합이 생성됩니다.
- combinationIndex가 0이면 어떤 비트도 설정되지 않아 공집합 {}이 됩니다.
이러한 방식은 재귀 호출 없이 반복문만으로 모든 부분집합을 생성할 수 있어 직관적이며, 시간 복잡도는 O(2ⁿ × n)입니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[
[],
[ 'x' ],
[ 'y' ],
[ 'x', 'y' ],
[ 'z' ],
[ 'x', 'z' ],
[ 'y', 'z' ],
[ 'x', 'y', 'z' ]
]
출력 결과에서 확인할 수 있듯이, 공집합부터 전체 집합까지 총 8개의 부분집합이 모두 포함되어 있습니다. 다만 원소 개수가 많아지면 부분집합의 수가 지수적으로 증가하므로, 실무에서는 입력 크기를 고려해 사용하는 것이 좋습니다.