Brute Force Algorithm 브루트 포스 알고리즘 JAVA

 

What is Brute Force Algorithm?

 

1990년대 청와대 해킹 사건이 발생했다. 당시 범인은 김재열이었고, 비밀번호를 뚫어던 사건이다. 당시 김재열 해킹과정에서 사용한 방법이 바로 Brute Force Algorithm 방식이다. 

 

비밀번호는 어디에나 존재한다. 인가된 사용자만 접근할 수 있도록 하기 위한 장치다. 이 비밀번호를 뚫기위한 최적의 방법이 Brute Force Algorithm이다. 어렵게 생각할 필요없이 가능한 모든 조건의 입력값을 하나씩 넣어보는 것이다. 키전수조사 혹은 무차별 대입 공격이라고도 부른다. 

 

Brute Force Algorithm은 항상 100%의 정확도를 보인다는 장점을 가진다. 암호학에서도 비밀번호를 뚫기 위한 가장 확실한 방법으로 인정받고 있다. 아라비안 숫자는 0~9까지의 숫자를 대입하면 되지만 로마자의 경우 경우의 수가 많기 때문에, 특정 규칙에 따른 우선순위를 정해서 대입규칙을 정하게 된다. 

 

Brute Force Algorithm의 가장 큰 장점은 완벽하게 병렬작업이 가능하다는 것이다. GPU를 사용하거나 여러대의 컴퓨터를 가지고 병렬 작업이 가능하다. 그럼에도 불구하고 현실에서는 병렬 작업으로 Brute Force Algorithm이 해결하지 못하는 경우가 많은데, 바로 복잡도(Complexity) 문제 때문이다.

 

Brute Force Algorithm의 가장 큰 문제는 복잡도에 있다. 요즘 비밀번호들은 모두 특수문자+대문자+8자리 이상의 조건들을 충족하는 경우가 많기 때문에, 비밀번호를 알아내는 시간이 굉장히 오래걸린다. 만약 위 조건의 비밀번호를 풀기 위한 텍스트 파일을 만들면 34^8Bit가 되고 1663GB가 된다.

 

 

Brute Force Algorith with JAVA

 

Brute Force Algorithm에서 가장 유명한 문제는 블랙잭 문제다. 주어진 N, M의 입력값은 주어지는 카드의 수와 가까이 접근해야 승리하는 블랙잭 21이 주어진다. 딜러가 제공한 N장의 카드 중 3장의 카드를 선택하여 그 합이 블랙잭 21의 숫자와 가장 유사한 숫자를 찾아서 외치는 문제다.

 

입력값 

5 21
5 6 7 8 9

출력값

21

JAVA 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Brute_force {
    public static void main(String[] args) {
        Scanner inputValue = new Scanner(System.in);

        String [] NM = inputValue.nextLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        String [] cardValueList = inputValue.nextLine().split(" ");

        ArrayList<Integer> card = new ArrayList<>();

        for(String num: cardValueList) {
            card.add(Integer.parseInt(num));
        }

        int max = 0;
        
        // 첫번째 카드 순회는 n-2까지 진행된다.
        for(int i=0;i<n-2;i++) {

            // 두번째 카드 순회는 첫번째 이후부터 n-1 까지 순회한다.
            for(int j=i+1; j<n-1;j++) {

                // 세번째 카드는 두번째 이후부터 n까지 순회한다.
                for(int k=j+1;k<n;k++) {
                    int sum = card.get(i)+card.get(j)+card.get(k);
                    
                    // 3장의 카드의 합이 m보다 작을 경우 max값을 계산한다.
                    // max와 sum의 값을 비교하면서 점점 max값은 m의 값에 근접한다.
                    if(sum <= m) {
                        max = Math.max(max, sum);
                    }
                    // max값이 m과 같으면 가장 가까운 값이기 때문에 즉시 Loop를 종료한다.
                    if(max == m) {
                        System.out.println(max);
                        return;
                    }
                }
            }
        }
        System.out.println(max);

    }
}

 

코드 풀이

1. 먼저 5장의 코드가 주어진다고 했을 때, 3장의 카드를 뽑게 된다. 입력받은 값을 N과 M으로 parsing해서 변수에 할당한다.
2. cardValueList에 주어진 5장의 카드 값을 할당하고 for문을 돌려서 card ArrayList에 할당한다.
3. 이제 3개의 for문을 중첩으로 돌려서 1번 카드 선택, 2번 카드 선택, 3번 카드 선택을 하면서 max값과 sum의 값을 비교하는 작업을 반복한다. 
4. 만약 sum의 값이 m값과 동일하다면 3개의 카드값의 합 중 가장 큰 숫자면서 m 이하 인 해답을 찾았기 때문에 바로 return한다.
5. 만약 sum의 값이 m 이하라면 max와 sum값을 계속 비교하면서 다른 카드를 뒤집는 작업이 반복된다.