[C++] 완전 탐색(1) - 부분 집합 구하기

본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다.

 

 

완전 탐색

거의 모든 알고리즘 문제를 해결하는 데 사용할 수 있는 일반적인 방법

 

완전 탐색은 정답에 대해 충분한 시간이 있다면 좋은 기술이다.

왜냐하면 완전 탐색은 검색을 구현하기 쉽고 항상 올바른 정답을 제공하기 때문이다.

 

하지만 완전 탐색이 너무 느리다면 그리디 알고리즘, 동적프로그래밍과 같은 다른 기술이 필요하다.

 

1. 부분 집합 구하기

먼저, n개 원소 집합의 모든 하위 집합을 생성하는 문제를 살펴보자.

예를 들어 {0, 1, 2}의 하위 집합은 "공집합, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}" 이다.

 

하위 집합을 생성하는 일반적인 방법에는 2가지가 있다.

1. 재귀
2. 정수의 비트 표현 활용

 

방법 1. Recursion

 

함수를 보고 단번에 이해하신다면, 대단한 사람....

 

함수 설명

1. search 함수가 매개 변수 k로 호출되면, k요소를 하위 집합에 포함하는 경우와 포함하지 않는 경우로 나뉜다.

2. 두 경우 모두 매개 변수 k+1로 호출한다.

3. k=n이면 함수는 모든 하위 집합 생성되었음을 알 수 있다.

void search(int k) {
	if(k == n) {
		// process subset
	} else {
		search(k+1);
		subset.push_back(k);
		search(k+1);
		subset.pop_back();
	}
}

 

이해를 돕고자, "n=3"인 경우의 코드 진행 과정을 나타낸 것입니다.

몇 가지 진행과정을 살펴보자면,

1. 공집합: search(0)/pop → search(1)/pop → search(2)/pop ▶ 원소 0, 1, 2를 모두 포함하지 않음(pop) ▶ 공집합

2. {2} : search(0)/pop → search(1)/pop → search(2)/push ▶ 원소 0, 1 포함 X, 원소 2 포함 ▶ {2}

 

요약하자면, 원소 0, 1, 2에 대해 각각 포함/미포함을 모든 경우를 재귀적으로 나타낸 것이다.

 

방법 2. 정수의 비트 표현 사용

 

n개 원소 집합의 각 하위 집합은 (0 ~ 2^n-1) 사이의 정수에 해당하는 n비트 시퀀스로 나타낼 수 있다.

(Shift 연산에 대한 이해가 필요합니다....)

Shift 연산은 말하자면, "1<<i" 가 시프트를 하여 "1*2의 i제곱" 을 나타낸다는 것입니다.

 

Q1. 3<<3은?

A1. 3*2^3

 

Q2. 24 >> 2은?

A2. 24/2^2

 

<< 은 2의 거듭제곱을 곱하는 것, >> 2의 거듭제곱을 나누는 것

#include <iostream>
#include <vector>

using namespace std;

int main() {
	
	int n;
	cin >> n;
	vector<int> subset;
	for(int b=0; b<(1<<n); b++) {
		//process subset
		
		for(int i=0; i<n; i++) {
			if(b&(1<<i))
			subset.push_back(i);
		}
	}
	for(int i=0; i<subset.size(); i++) {
		cout << subset[i]<< " ";
	}
}

// 0, 1, (0 1), 2, (0 2), (1 2), (0 1 2)