양의 정수로 이루어진 배열이 주어졌을 때, 각 부분 집합이 중복되지 않는 짝수만을 포함하도록 만들 수 있는 부분 집합의 개수를 구하는 것이 목표입니다. 같은 원소를 가진 집합은 하나로 취급합니다. 예를 들어 [2,4,6]과 [6,2,4]는 동일한 집합입니다.
문제 이해하기
예제를 통해 문제를 살펴보겠습니다.
입력 − arr[] = {1, 3, 5, 7, 8, 3, 2}
출력 − 서로 다른 짝수를 가진 부분 집합의 개수: 3
설명 − 가능한 부분 집합은 [2], [8], [2,8] 입니다.
입력 − arr[] = {2, 4, 6}
출력 − 서로 다른 짝수를 가진 부분 집합의 개수: 7
설명 − 가능한 부분 집합은 [2], [4], [6], [2,4], [2,6], [4,6], [2,4,6] 입니다.
해결 접근 방법
핵심 아이디어는 배열에 존재하는 서로 다른 짝수의 개수를 먼저 구하는 것입니다. 중복 없는 n개의 짝수가 있다면, 이들로 만들 수 있는 비어 있지 않은 부분 집합의 개수는 다음 공식으로 계산됩니다.
부분 집합의 개수 = 2n − 1
전체 부분 집합의 개수(2n)에서 공집합 하나를 제외하기 때문에 1을 빼줍니다.
알고리즘 단계
- 숫자 배열 arr[]를 입력으로 받습니다.
- subset_even(int arr[], int size) 함수는 배열을 받아 조건을 만족하는 부분 집합의 개수를 반환합니다.
- 초기 count 값을 0으로 설정합니다.
- 짝수를 저장하기 위해 unordered_set<int> 타입의 un_set을 생성합니다. set은 자동으로 중복을 제거해 줍니다.
- for 반복문으로 i = 0부터 i < size까지 배열을 순회합니다.
- arr[i] % 2 == 0이면 짝수이므로 un_set에 삽입합니다.
- count = un_set.size()로 서로 다른 짝수의 개수를 구합니다.
- count = pow(2, count) − 1 공식을 적용해 최종 결과를 계산합니다.
- count를 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int subset_even(int arr[], int size){
int count = 0;
unordered_set<int> un_set;
for(int i = 0; i < size; i++){
if (arr[i] % 2 == 0){
un_set.insert(arr[i]);
}
}
count = un_set.size();
count = pow(2, count) - 1;
return count;
}
int main(){
int arr[] = {10, 4, 21, 3, 5, 7, 6, 8};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"서로 다른 짝수를 가진 부분 집합의 개수: "<<subset_even(arr, size);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
서로 다른 짝수를 가진 부분 집합의 개수: 15
코드 설명 및 복잡도 분석
위 예제 배열 {10, 4, 21, 3, 5, 7, 6, 8}에서 짝수는 10, 4, 6, 8로 총 4개입니다. 따라서 부분 집합의 개수는 24 − 1 = 15가 됩니다.
- 시간 복잡도: O(n) — 배열을 한 번 순회하며 set에 삽입합니다.
- 공간 복잡도: O(k) — k는 서로 다른 짝수의 개수입니다.
unordered_set을 사용하면 중복 제거가 자동으로 처리되므로 코드가 간결해지며, 삽입과 조회 모두 평균 O(1)의 성능을 보장합니다.