[자료구조] 완전 탐색 : 브루트 포스 알고리즘

브루트 포스(brute force)

완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

브루트 포스의 장점은 예외없이 100%의 확률로 정답을 찾아낸다는 것이다. 대부분 반복문과 조건문을 통하여 답을 도출한다.

 

모든 경우의 수를 전부 탐색하기 때문에, 100%의 확률로 정답을 찾아내지만,

모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다.

 

 

완전 탐색과 브루트 포스 알고리즘의 차이

 

• 완전 탐색 알고리즘 : 모든 경우의 수를 전부 탐색하는 방식의 알고리즘, 결과보다는 탐색 과정에 중점을 둔다.
• 브루트 포스 알고리즘 : 문제를 해결하기 위해, 모든 경우를 탐색하고 답을 도출하는 알고리즘, 결과를 찾는 것에 중점을 둔다.

 

브루트 포스의 기본적인 도구

• 선형 구조를 전체적으로 탐색하는 순차 탐색
• 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breadth First Search)

 * 너비 우선 탐색은 브루트 포스와 관련이 있고, 깊이 우선 탐색은 백트래킹과 관련이 있다.

 

브루트 포스 알고리즘의 사용 조건

 

• 문제에서 달성하고자 하는 솔루션이 잘 정의 되어 있어야 한다.
• 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

 

문제 해결 방법

• 주어진 문제를 선형 구조로 구조화 한다.
• 구조화된 문제 공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
• 구성된 해를 정리한다.