[알고리즘 - 이론] 브루트 포스(Brute Force)

브루트 포스(Brute Force)란?

브루트 포스란
브루트(Brute)난폭한/무식한 + 포스(Force) 힘
두 단어를 합친것으로 단어 뜻 그대로 무식하게 해결한다는 뜻이다.
간단하게 설명하자면 모든 경우의 수를 무식하게 전부 탐색한다는 뜻으로, 전체탐색, 완전탐색이라고도 불린다.

브루트 포스 예시

브루트 포스는 모두 다 해보는 알고리즘이다.
'1부터 100까지의 합을 구하라'
위 문제는 1부터 100까지 모든 경우의 수를 전부 더해야 하는 예시문제이다.
컴퓨터의 연산속도는 사람보다 비교도 할 수 없이 빠르기 때문에 1부터 100까지 모두 더한다해도 시간이 얼마 걸리지 않을것이다. 하지만, 브루트 포스의 문제점은 자릿수가 커질수록 발생한다.
만약 1부터 100까지가 아닌, 1부터 1조까지 더한다고 해보자.
숫자 하나를 더하면서 1번의 연산을 하는데, 1조까지 모두 더해준다면 1조 번 계산을 해야한다.
일반적으로 컴퓨터는 1초에 약 1억 번의 연산이 가능하다.
1부터 1조까지의 합을 구하려면 10000초 = 약 167분이나 걸린다.

브루트 포스의 장점

1. 원하는 경우를 무조건 찾을 수 있다.
   원하는 경우가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 원하는 경우를 찾을 수 있다.
2. 알고리즘을 설계하고 구현하기가 쉽다.
   복잡한 설계없이 주어진 모든 경우의 수를 탐색하면 되기 때문에 간단하게 설계할 수 있다.

브루트 포스의 단점

1. 시간과 메모리 효율이 매우 좋지않다.
   모든 경우의 수를 하나도 빠짐없이 전부 탐색하기 때문에 시간복잡도는 O(M^N)이다.
   시간복잡도가 제곱수만큼 증가하기 때문에, 시간도 메모리 효율도 매우 좋지않다.

브루트포스 백준문제

블랙잭(브론즈2)

https://www.acmicpc.net/problem/2798

체스판 다시 칠하기(실버4)

https://www.acmicpc.net/problem/1018