브루트포스는 말 그대로 단순무식하게 수학 문제를 푸는 방법인 계산 노가다의 학술적 개념으로, 무식하게 탐색하는 방법이다.
그만큼 시간과 자원이 엄청나게 들어 얼핏 보면 무식하고 비효율적이라고 생각할 수 있지만, 모든 경우의 수를 다 해보는 것이기 때문에 정확도 100%를 보장한다.
설계
브루트 포스로 문제를 풀기 위해서는 3단계 정도로 생각할 수 있다고 한다.
- 문제의 가능한 경우의 수를 계산해본다.
- 가능한 모든 방법을 다 만들어본다.
- 각각의 방법을 이용해 답을 구해본다.
1. 문제의 가능한 경우의 수를 계산해본다.
먼저 문제에서 주어진 시간복잡도 내로 해결해야하기 때문에 시간 복잡도를 대략적으로 추정해보는 과정에 해당한다.
2. 가능한 모든 방법을 다 만들어본다.
이때 중요한 것은 단 한 가지 경우라도 빠짐없이 만들어야 한다는 점인데, 구현 방법은 여러 가지가 있다.
- 일일이 작성하는 방법
- for, while 등 반복문을 사용하는 방법
- 순열을 사용하는 방법
- 재귀 호출을 사용하는 방법
- 비트마스트를 사용하는 방법
3. 각각의 방법을 이용해 답을 구해본다.
위에서 생각한 방법을 실행해보면 답은 나오는 경우가 많다.
단점
브루트 포스 문제의 시간복잡도는 보통 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간복잡도)이다.
따라서 문제의 복잡도에 매우 민감하며, 탐색하고자 하는 값의 범위가 넓은 경우, 알고리즘 실행시간이 오래 걸린다.
