[0626] 브루트포스

01. 개념

• 브루트 포스는 모든 경우의 수를 다 해보는 것이다.

• 이 때, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다.

• 예를 들어, 비밀번호가 4자리이고, 숫자로만 이루어져 있다고 한다면 

• 0000부터 9999까지 다 입력해보면 된다.

• 경우의 수가 10,000가지 이다.

• 사람이 직접 비밀번호를 입력하는데 1초가 걸린다면 10,000초 = 2.7시간 정도 걸린다.

02. 브루트 포스 3단계 풀이법

 

1. 문제의 가능한 경우의 수를 계산한다.

- 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다.

 

2. 가능한 모든 방법을 다 만들어본다.

- 하나도 빠짐 없이 만들어야 한다.

- 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀호출 사용, 비트마스크 사용이 있다.

 

3. 각각의 방법을 이용해 답을 구해본다. 

- 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다.

 

▶ 브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간 복잡도 )가 걸린다.