알고리즘 문제 유형(부분집합)
in Algorithm
부분집합의 개수를 구해보자
본 알고리즘 유형은 C++를 이용하여 해결한다.
이 글을 쓰게 된 이유는 간혹 브루트 포스 문제를 풀거나 정렬 문제를 풀 때 부분집합 의 개수를 묻는 문제가 간혹 있었는데 그럴 때마다 항상 어떻게 구해야되지 라는 생각이 들어 아예 정리하기 위해 쓰고 있다.
문제 설명
문제는 이런식으로 주어진다.
아무개는 랜덤값 K 를 받아 배열 A 에서 원소가 K개만큼 들어있는 부분집합의 총 개수를 구하려고 합니다. [1,2] 나 [2,1] 은 같은 부분집합으로 구분됩니다. 구해보세요~
예제
| array | K | return |
|---|---|---|
| [1,2,3] | 2 | [1,2], [1,3], [2,3] |
| [1,8,8,8] | 3 | [1,8,8], [8,8,8] |
문제 해결
노가다 버전 : for문을 이용한 해결법
시간복잡도 면에서 최악의 해결법이다. 같이 코드를 보자
vector<vector<int>> solution(vector<int>& array, int K) {
//이 코드에서는 K가 4이라고 가정하겠습니다.
vector<vector<int>> ret;
vector<int> temp(4,0);
int n = array.size();
for(int i=0;i<n;++i)
for(int j=i+1;j<<n;++j)
for(int k=j+1;k<n;++k)
for(int l=k+1;l<n;++l){
temp = {i, j, k, l};
ret.push_back(temp);
}
return ret;
}
이 코드는 부분집합들을 2차원 배열로 리턴해준다. 다만 이 방법은 리스크를 감당하기에는 너무 비효율적이다.
- 중첩된 for문
- 만약 K값이 4가 아니라 5라면 for문을 그에 맞게 늘려야되는 부분
위와 같은 사유로 안 쓰는 게 나은 해결법이다. (다만 K값이 고정되어 있는 경우 다른 해결법이 도무지 생각나지 않는다면 이 방법도 괜찮다. 단 K가 작아야 됨)
똑똑한 방법 : 재귀함수
이 방법은 앞서 소개한 방법에서 for문을 하나를 함수로 떼어낸 것이다. 이 방법은 최악의 해결법에서 2번째 단점을 해결해준다.
vector<int> ret;
void solution(int n, vector<int> &picked, int K) { // n은 원소의 개수
if(K == 0) return;
// 고를 수 있는 가장 작은 원소 하나를 고른다.
int smallest = ret.empty() ? 0 : ret.back() + 1;
//아래 단계에서 원소 하나를 고른다.
for(int next = smallest; next < n; ++next) {
ret.push_back(next);
ret(picked, K-1);
ret.pop_back();
}
}
위와 같은 방법으로 첫 번째 방법에서 K값에 따른 그에 비례하는 for문을 줄일 수 있다. 다만 아쉽게 전역변수를 써야하지만 오로지 코테용으로만 쓸 거면 나쁘지 않은 선택이다. 오늘은 간단하게 c++ 을 이용하여 부분집합을 구하는 방법을 알아봤다. 부분집합 문제는 가끔씩 보이는 문제인데 항상 아이디어가 생각나지 않았다. 이 글을 통해 다들 코테 공부를 열심히 하길 바란다.
