브루트 포스의 사전적 의미는 brute: 난폭한, 무식한 / force: 힘 난폭한 힘이다.
무식하게 가능한 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만을 가져온다. 완전 탐색 알고리즘이라고 부르기도 한다.
알고리즘 설계의 기본적인 접근 방법은 해가 하나 이상 존재한다는 가정을 세우고, 해가 존재할 것으로 예상되는 모든 범위를 전체 탐색하는 것이다.
따라서 항상 100%의 확률로 정답만을 출력한다.
- 정답만을 출력한다.
- 알고리즘을 설계하고 구현하기 쉽다.
- 실행 시간이 오래 걸린다.
- 메모리 사용이 비효율적이다.
브루트 포스는 자료 구조에 따라 선형 구조와 비선형 구조로 나눌 수 있다.
- 선형 구조 - 순차 탐색
- 주어진 문제를 선형 구조로 구조화한다.
- 구조화된 문제를 적절한 방법으로 해를 구할 때까지 탐색한다.
- 탐색한 해를 출력 조건에 맞게 정리한다.
- 비선형 구조 - DFS, BFS (DFS는 백트래킹, BFS는 브루트 포스와 관련이 깊다)
참고
https://hcr3066.tistory.com/26 https://foreverhappiness.tistory.com/104