5. Brute Force Algorithm

  도둑이 0~9까지 숫자로 되어있는 다섯자리 비밀번호를 풀어야 한다고 가정해보자. 그리고, 도둑은 그 비밀번호에 대한 사전 정보가 전혀 없다고 가정하다. 이때, 선택할 수 있는 방법은 무엇일까? 바로 모든 다섯자리 숫자인 10만개를 순서대로 하나 쳐보는 것이다.

1. Brute Force란?

   Brute Force 알고리즘은 가능한 경우의 수를 모두 입력하는 것이다. 이게 무슨 알고리즘이냐고 할 수 있겠지만, Brute Force 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답을 출력해낸다. 앞에서 말한 예시대로 도둑이 10만번에 번호를 누르게 된다면 언젠가는 분명히 열린다. 00000~99999까지 계속 입력하다보면 비밀번호를 알아낼 수 있다. 사전 정보가 없을 때라면 무조건 선택 할 수 밖에 없게 된다.

  Brute Force를 이용해서 1부터 N까지의 숫자를 더한 값을 구하는 코드를 짠다고 가정하자 그렇다면 아래와 같이 나온다.

import java.util.Scanner;
 
public class Solution {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        int Answer=0;
        
        for(int i=1; i<=N; i++){
            Answer+=i;
        }
 
        System.out.println(Answer);
        
    }
 
}

  an

   Brute Force 알고리즘은 매우 간단하게 코딩을 짤 수 있고, 정답도 확실하게 찾아 낼 수 있다.

2. Brute Force의 사용

  Brute Force 알고리즘은 확실한 방법이지만 자원이 문제이다. 앞서 도둑이 겨우 다섯자리의 숫자를 찾아내는데 10만번의 Input이 필요했던 것처럼, 숫자가 하나만 추가되더라고 입력 횟수는 기하급수적으로 올라간다. 8자리의 숫자를 찾아야 한다면 1억번, 12자리의 숫자를 찾아야 한다면 1조번의 입력이 필요하다. 컴퓨터 비밀번호 처럼 특수 문자나 알파벳 입력이 가능하다고 하면 Brute Force는 거의 무용지물에 가깝게 된다. 물론 자원이 충분하다면 이론상 최강인 알고리즘이다.

  Brute Force알고리즘의 일종으로 사전 공격(Dictionary Attack)방법이 있다. 예를들어, 비밀번호를 Brute Force알고리즘으로 찾는다고 할 때, 000000 부터 시작하는게 아닌 abc, qwerty, q1w2e3 처럼 사람들이 주로 많이 사용하는 비밀번호 부터 공략하는 것을 의미한다. 시작점을 달리 해 Brute Force알고리즘이 가진 단점을 확률적 모형에 기반해 성능을 개선 할 수 있는 방법이다. 

  매우 단순한 알고리즘인 Brute Force를 배우는 이유는 크게 두가지 이다. 우리가 반드시 풀어야할 문제가 있고, 사전 정보를 얻을 수 없는 방법이 전혀 없다면 어쩔 수 없이 Brute Force알고리즘을 사용해야한다. 이 방법 이외에는 달리 방법이 없다. 두번째는 다른 알고리즘과의 성능 비교를 위해 사용된다. 성능은 크게 2가지로 나눌수 있는데 정확도와 복잡도이다. Brute Force는 다른 알고리즘보다 정확도는 100%로 가장 좋고, 반면에 복잡되는 가장 안좋다. 어떤 알고리즘도 Brute Force보다 정확도가 높지 않고, 복잡도가 나쁘지 않다. (동일 할 수는 있다.) Brute Force를 기반으로 얼마나 정확한지와 빠른지를 비교하면서 알고리즘의 성능을 파악 할 수 있다.