[알고리즘] 브루트 포스(Brute Force) 문제 판별법
브루트 포스 알고리즘은 단어 그대로 Brute (무식한), Force (힘) 를 해석하여 무식하게 모든 경우의 수를 비교하여 해답을 찾는 알고리즘이다.
전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.
모든 경우를 계산하기 때문에 단순히 모든 경우의 수를 비교하는 알고리즘을 설계하고 구현하기에 비교적 쉽고, 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 또한 강력한 장점은 어떤 경우에도 예외 없이 100%의 확률로 정답만을 출력할 수 있는 점이다.
그러나, 모든 경우의 수를 연산하는 만큼 알고리즘 실행 시간이 매우 오래 걸리고, 메모리 효율면에서도 매우 비효율적이며 계산 비용이 높다.
따라서 문제를 파악할 때 브루트포스 알고리즘으로 풀이할 수 있는지를 판단해야 하는데, 이는 입력값(N)과 제한 시간을 보고 비교하면 된다.
컴퓨터가 1초 당 1억번의 연산횟수를 감당해낸다고 할 때, N번의 입력 값을 가지고 모든 경우의 수를 전부 계산하여 제한시간 안에 수행될 수 있는가를 판단한다.
https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
예를 들어, 3 <= N <= 100 의 정수 N을 입력받아, N 개수의 숫자를 추가로 입력받고, 그 안에서 숫자를 하나씩 뽑으며 숫자를 조합하는 문제가 있다.
숫자는 총 3가지를 뽑아서 계산한다고 할 때, N의 최대 입력값인 100을 입력받았다고 가정하자.
100개의 숫자 중, 3가지 숫자를 뽑으므로 100개중 1개, 100개중 1개, 100개중 1개 -> 100의 3제곱 만큼의 연산이 수행된다.
해당 문제의 제한시간은 1초로 나와있으므로 총 1억번을 넘기지 않으면 되는데, 100의 3제곱은 백만(1,000,000)이므로 1억을 넘기지 않는다.
따라서 해당 문제는 모든 경우의 수를 비교하는 3중 for문을 돌면서 풀어도 시간제한에 걸리지 않고 성공적인 브루트 포스 알고리즘을 사용할 수 있다!
이런식으로 입력값 N을 비교하며 브루트 포스 적용 가능한 문제인지 판별하자.