브루트 포스

목표

• 브루트 포스 알고리즘의 특징과 한계를 설명할 수 있다.

 

1. 브루트 포스란 무엇인가?

브루트 포스는 모든 경우의 수를 다 시도해보는 방법이다.

이론상으로는 모든 경우를 다 시도해보기 때문에 못 푸는 문제가 없지만 시간상의 문제로 인해 불가능하다고 판단해야 하는 경우가 많다.
브루트포스로 해결할 수 있는 문제 중 가장 친숙한 예로는 자물쇠 풀기가 있다. 
비밀번호가 4자리인 자물쇠를 푸는방법은 어떤것이 있을까?
물론 비밀번호를 알고있다면 가장 빠르게 풀겠지만, 모른다고해서 못푸는것은 아니다.
왜냐하면 모든 4자리 경우의수를 자물쇠에 대입해보면 되기 때문이다.
4자리 비밀번호를 맞춰야 하는 경우, 0000 ~ 9999까지 총 10,000개를 시도해보면 답을 구할 수 있다.
비밀번호 입력을 1번 시도하는데 드는 시간이 1초라고 한다면 10,000초 만에 해결할 수 있으므로 충분히 시도해볼 만하다.
그런데 만약 자물쇠의 비밀번호가 12자리인 경우라면 어떻게될까?
000000000000 ~ 999999999999까지는 총 경우의 수가 1,000,000,000,000(1조)가지가 존재한다.
위와 동일하게 한번 입력하는데 1초가 걸린다고 했을 때, 모든 경우를 시도해보는데 31,709년이 걸린다.
그렇기 때문에 브루트 포스는 모든 문제를 해결할 수 있는 방법이 아니며 경우의 수가 적은 경우에만 사용할 수 있는 방법이다. 

 

2. 브루트 포스로 문제 해결을 하는 방법

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

브루트 포스로 해결을 할지 말지 정하는 가장 중요한 판단기준이기 때문에 반드시 계산해봐야 한다.

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

경우의 수가 브루트 포스로 해결해 볼만한 크기라면, 모든 경우를 빠뜨리지 않고 다 파악해야 한다.

3. 적절한 방법을 이용해 모든 경우의 수를 시도해 본다.

반복문, 순열, 재귀, 비트 마스크 중 적절한 방법을 택해 모든 경우의 수를 대입해서 답을 구한다.