[알고리즘]완전탐색(Brute-force)

브루트포스(brute force)알고리즘, 완전탐색이란 가능한 경우를 모두 탐색해보는 방법입니다.

예시로는 해킹 시 모든 가능한 경우의 비밀번호를 다 넣어보는 것 등이 해당됩니다.

 

특정 알고리즘을 쓰게 하기 위해 시간제한이 짧은 경우엔 시간초과가 나지만,

때로는 완전탐색을 하는 방법이 간단하고 확실한 방법일 수 있습니다.

 

 

예제 (c++)

백준 2309-일곱 난쟁이

9명의 키가 입력으로 주어지는데 키 합이 100이 되는 7명의 키를 출력하는 문제입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	vector <int> v;
	int sum = 0;
	int one = 0;
	int two = 0;

	for (int i = 0; i < 9; i++) {
		int a;
		cin >> a;

		v.push_back(a);
	}
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		for (int j = i + 1; j < v.size(); j++) {
			sum = 0;
			for (int k = 0; k < v.size(); k++) {
				if (k != i && k != j) {
					sum += v[k];
				}
			}
			if (sum == 100) {
				one = i;
				two = j;
				break;
			}
		}
	}
	for (int i = 0; i < v.size(); i++) {
		if (i != one && i != two) {
			cout << v[i] << endl;
		}
	}
}

9개의 수에서 2개를 제외시키고 7개의 합이 100이 되는 경우를 모두 확인해서 100이 되면

포함되지 않았던 2개가 아닌 7개의 수를 출력하도록 했습니다.

 

이 예시에서는 모든 가능한 7개 수의 조합을 보고 100인지 확인하고 있으므로 

브루트포스 알고리즘이 적용된 것을 알 수 있습니다.

 

장점

• 복잡한 알고리즘이 사용되지 않아 코드가 간결해집니다.
• 확실히 답인 값을 구할 수 있는 알고리즘 입니다.

 

단점

• 다른 알고리즘을 사용하는 것보다 시간이 오래 걸릴 수 있습니다.