가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법
즉, 무식하게 가능한 거 다 해보겠다는 방법
이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.
예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것이다.(최대 10,000번의 시도로 해결 가능)
하지만, Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다.
- 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 )
- 효율적으로 동작하는가?
위 2가지의 규칙에 대해서 생각할 때, 1번은 만족될 수 있는 가장 확실한 방법이겠으나 대부분의 경우 2번의 경우 때문에 이 방법이 사용되는데는 제한이 따른다.
따라서 경우에따라 dp를 해결해서 효율성을 해결하기도한다.
N의 최대 범위에따라 주어진 시간 이내에 풀어낼 수 없는 경우가 생길 수 있다.
따라서, 완전탐색 기법을 사용 시에는 그 문제에 대한 파악이 중요하다.
활용 방법
우선 완전탐색 기법으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행한다.
1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2) 가능한 모든 방법을 다 고려한다.
3) 실제 답을 구할 수 있는지 적용한다.
여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있다. (아래의 기법을 사용하는 완전탐색으로 보면된다)
① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출 (백트래킹)
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법
브루트포스는 시간복잡도가 커 좋은 알고리즘 방식이 아니기때문에, 실제 알고리즘을 풀땐 이 문제가 브루트포스로 가능한지 확인 후 불가능하다면 어떤 알고리즘을 적용해서 시간복잡도를 줄일지 확인해야한다.(DP,누적합,이분탐색 등등)
사실 브루트포스는 알고리즘으로서 정형화된 틀은 없기때문에 따로 알려줄건 없다.
