브루트 포스(Brute Force, 완전 탐색)

 브루트 포스(Brute Force)는 거의 모든 문제에 사용할 수 있는 기법으로 완전 탐색이라고도 합니다.

 이 기법은 이름처럼,

"맹목적으로, 모든 경우의 수를 탐색하여 결과를 도출하는 기법"

 입니다. 이 기법은 어쩔수없이 모든 경우의 수를 탐색해 봐야만 하는 경우나, 모든 경우의 수를 요구하는 문제에서 주로 사용됩니다.

 예를들어, 1부터 100까지의 합을 구하는 문제가 있을 때 아래와 같이 모든 경우의 수( 1부터 100까지) 탐색하여 그 합을 구하는 방식이 브루트 포스가 될 수 있습니다.

sum = 0
for i in range(1, 101):
    sum += i

 이 뿐 아니라 가장 대표적인 예시로, 순열을 구하는 문제가 있습니다.

 예를들어, 1부터 5까지의 수를 이용해 모든 수에 대한 순열을 구하는 문제가 있다고 합시다.

 이를 직관적으로, 

iterable, visited = [1,2,3,4,5], [False] * 5
 
def get_permutations( _currentIndex, _permutation):
    if _currentIndex == 5 :
        print( _permutation)
        return
 
    for index, value in enumerate( iterable):
        if not visited[index]:
            visited[index], _permutation[ _currentIndex] = True, value
            get_permutations( _currentIndex + 1, _permutation)
            visited[index] = False
 
if __name__ == '__main__':
    get_permutations( 0, [None] * 5)

 위와 같이 재귀적인 특성을 이용해 구할 수 있습니다.

 브루트 포스는 어쩌면 굉장히 단순한 기법이며 문제해결에 대하여 첫째로 생각할 단계입니다.

 문제에서 요구하는 방법을 직관적으로 이해하여, 모든 경우의 수를 확인할 수 있도록 어떻게 프로그래밍을 진행할까에 대한 고민을 시작으로. 모든 경우의 수를 확인하지 않도록 가지치기(Branch and Bound)를 사용하며 그 외의 알고리즘으로 확장시켜 나가면 됩니다.

 P.S. 

 파이썬의 경우 아래와 같이 모든 경우에 대한 순열을 구하는 함수를 제공합니다.

import itertools
 
iterable = [1,2,3,4,5]
result = itertools.permutations( iterable)
for permutation in result:
    print( permutation)

 C++의 경우에는 아래와 같이 next_permutation()를 사용하셔도 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){
    vector<int> iterable(5);
 
    for( int index = 0; index < 5; index++)
        iterable[index] = index * 2;
 
    do{
        for(int index = 0; index < 5; index++)
            cout << iterable[index] << " ";
        cout << endl;
    }while( next_permutation( iterable.begin(), iterable.end()) );
 
    return 0;
}