완전탐색

본 글은 프로그래밍 대회에서 배우는 문제해결전략 책과 다른 완전 탐색 구현방법을 보고 정리하는 글이다.

 

완전 탐색은 다른 말로 brute-force 직역하면 무차별 대입, 모든 경우를 다 구해보는 것이다.

컴퓨터의 장점을 가장 잘 이용하는 방법으로 단순한 문제들을 빠르게 계산할 수 있기 때문에 효율적인 알고리즘을 설계하기 전에 생각해보는 방법이다.

 

흔히 재귀 호출로 쉽게 구현할 수 있는데, 기저 사례 (base case)의 선택과 상태 공간 트리의 순회방법을 어떻게 구현할 지 고민해야 한다.

(상태공간트리 : 완전 탐색에서 해의 조합들을 트리 (tree) 형태로 나타낼 수 있는데, 부분 문제들을 한 눈에 알 수 있다.)

 

또한 부분 문제가 또 다른 부분 문제를 구하는 과정에서 쓰일 수 있기 때문에 메모이제이션과 결합하여 연산 속도를 줄이는 방법도 사용될 수 있다.

//n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
void pick(int n, vector<int>& picked, int toPick)
{
	//기저사례 : 더 이상 문제를 분할할 수 없음 (더 고를 원소가 없음)
	if(toPick == 0){ printPicked(picked); return; }
    //순회 방법 : 가장 작은 원소부터 고름
    int smallest = picked.empty() ? 0 : picked.back() + 1;
    //반복문으로 순회 구현
    for(int next = smallest; next < n; ++next){
    	picked.push_back(next);
        pick(n, picked, toPick - 1);
        picked.pop_back();
    }
}