브루트 포스(Brute Force)

브루트 포스(Brute Force)

브루트 포스는 '모든 경우의 수'를 다 해보는 것이다. 
이 때, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다.

( * '모든 경우의 수' : 가능한 벙법 )
따라서 브루트 포스 문제의 경우 '모든 경우의 수'가 몇가지 나오는지 알아보는 것이 상당히 중요


브루트 포스는 모든 방법을 1번씩 시도해보기 때문에 아래 3가지 단계를 생각해볼 수 있다.

1. 문제의 가능한 경우의 수를 계산해본다.
    • 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다.
2. 가능한 모든 방법을 다 만들어본다.
    • 하나도 빠짐 없이 만들어야 한다.
    • 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다.
3. 각각의 방법을 이용해 답을 구해본다.
    • 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 *방법 1개를 시도해보는데 걸리는 시간복잡도)가 걸린다.

여기서 재귀 호출 사용하는 방법이 가장 중요하다. 순열이나 비트마스크 사용을 몰라도 재귀 호출을 사용 할 줄 알면 대체가 가능하기 때문이다.