부르트포스(Brute Force)

일반적으로 SW를 개발하면서 결정 문제(decision problem), 탐색 문제(search problem), 카운팅 문제(couting problem), 최적화 문제(optimization problem), 함수형 문제(function problem)  문제등 다양한 문제해결(Problem Solving)이 필요하다. 

문제해결을 위해 단순한 자료구조나 알고리즘을 이용하면 되는 경우도 있지만 한개이상의 알고리즘을 복합적으로 사용하여 풀어야 하는 경우도 많이 있다. 

 

부르트포스(Brute Force) 란 위와 같은 다양한 문제해결을 위해 어떤 방식으로 접근할 것인가? 인데  결론 부터 말하면 문제해결을 위해  모든 가능한 경우의 수를 모두 뒤져서 해를 얻는 한마디로 좀 무식한 방법 이다. 

대표적으로 어떤 해커가 나의 비밀번호를 찾아내기 위해 알파벳, 기호, 숫자로 이루어질수 있는 가능한 모든 비밀번호 경우의수를 하나씩 시도해보는 것이다. 답이 언제 나올지는 모르겠으나 가능한 모든 값을 대입하면서 시도하는 것으로 보통  무차별 대입 공격(brute force attac)이라 부른다.

 

선형(순차) 탐색(Linear Search)이나  버블(거품)정렬(Bubble Sort) 알고리즘들도 원하는 문제를 해결하기위해 선형공간에서 답이 언제 나올지는 모르나 모든 원소들을 하나씩 비교해가면서 최종적으로 해를 찾고자 하는 부르트포스(Brute Force)의 종류이다.

 

고등학교때 경우의 수를 구하는 문제를 풀다가 잘 모르겠으면 시험지에 모든 경우의 수를 다 적어가면서 해를 찾았던 경험이 있다면 이미 부르트포스 방법으로 문제를 푼것이다.

 

부르트포스가 모든 가능한 값을 대입하면서 풀기 때문에 원하는 답을 언제가는 얻겠지만 메모리 공간이나 성능면에서 떨어질수 있다.
즉, 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다는 것이다.

 

경우의 수가 문제의 복잡도에 따라 기하급수적으로 증가하는 경우, 문제를 해결하는 데에 필요한 자원 역시 기하급수적으로 증가하기 때문에 보통은 부르트포스로 풀지 않고 동적프로그래밍(DP)로 우회하는 방법을 쓰기도 한다.