C++ 알고리즘 - 브루트 포스

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

예를 들어, 비밀번호가 4자리이고 숫자로만 이루어져있다고 한다면 0000부터 9999까지 10000가지의 경우의 수를 다 해보면 된다!! (1억 개에 대충 1초 정도 걸리니까 10000가지면 엄청 짧은 시간 안에 계산 가능!!)

그런데 비밀번호가 12자리이고 숫자로만 이루어져있다면 000000000000에서 9999999999999까지 경우의 수를 다 구하는 건 어렵다!!!

 

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

 

브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다.

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

- 직접 계산을 통해서 구한다.

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

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

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

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

 

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