완전 탐색(Brute Force - with. 백준 일곱난쟁이)

 

 

 

알고리즘 문제를 해결하기 위해 가장 쉬운 방법 중 하나로 완전 탐색을 떠올릴 수 있다. 이 알고리즘은 간단하게 모든 경우의 수를 탐색하는 방법으로 구현하기 쉬운만큼 시간은 최대로 사용하게 된다. 

 

완전 탐색으로 풀 수 있는 문제 중 백준의 일곱 난쟁이 문제의 코드를 예시로 들어보겠다.

 

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

문제를 간략하게 설명하자면 아홉 난쟁이의 키가 주어졌을 때 일곱 난쟁이의 키의 합이 100이 되는 경우를 찾아 각 난쟁이의 키를 오름차순으로 출력하는 문제이다. 이때 완전 탐색으로 풀 수 있다는 전제 조건은 입력의 범위를 확인하면 파악할 수 있다. 입력이 최대 9명이고 그 중 2명을 제외한 7명을 뽑는 경우의 수 이므로 9C2 = 36가지를 생각할 수 있다. 

 

 

이 경우 중첩 반복문으로 모든 경우를 탐색할 수 있다.  다음 코드를 확인해보면 완전 탐색이 적용된 것을 확인할 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int arr[9], sum = 0;
	for(int i = 0; i<9; i++) {
		cin>>arr[i];
		sum += arr[i];
	}

	sort(arr, arr+9);
    	for(int i = 0; i<8; i++) {
    		for(int j = 1; j<9; j++) {
    			if(i!=j && sum - arr[i] - arr[j] == 100) {
    				for(int k = 0; k<9; k++) {
    					if(k == i || k == j) continue;
						cout<<arr[k]<<"\n";
					}
					return 0; 
				}
			}
    	
		} 
}

 

9명의 난쟁이 키를 입력받은 뒤 오름차순 정렬하여 중복을 제외하고 9명 중 7명을 뽑아 100이 되었을 때 순차적으로 출력하는 코드임을 알 수 있다. 참고로 c++ STL의 sort 알고리즘 시간 복잡도는 O(nlogn) 이므로 문제를 푸는 데에는 영향이 없다. 위의 조건문이 성립할 때 최악의 경우 시간복잡도가 O(n^3) 이 나오더라도 문제의 입력 범위를 비교해보면 충분히 해결할 수 있는 문제이기에 완전 탐색이 적용될 수 있는 것이다. 

 

어떤 문제이든 처음으로 떠올리는 방법이 모든 경우의 수를 탐색하는 방법인데 굉장히 쉬운만큼 실제 코딩테스트나 대회에서도 완전 탐색으로 풀리는 문제가 많이 나오지는 않는다. 그러나 반대로 알고리즘 중 가장 기본적인 방법이면서도 완전탐색으로 풀리는 문제가 일부 존재하기에 이해하고 넘어가는 게 좋다고 생각한다.