[Brute Force] 브루트 포스 설명과 간단 코테 풀이

브루트 포스(Brute Force)

• 알고리즘에서의 브루트 포스(Breute Force)에 관한 이야기 이다
• 공격기법 부르트 포스에 대한 이야기가 아니다. Brute Force Attack

Brute : 난폭한 / Force : 힘 두 의미를 합하면 난폭한 힘(?)으로 해석이 된다.

간단히 설명하자면 무식하게 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 일명 노가다...

• 이 알고리즘의 가장 큰 특징은 모든 영역을 전체 탐색하는 방법이다.
• 전체 탐색하는 방법으로는 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 가 기본적인 도구이다.
• 어떤 방식으로든 전체 탐색으로 문제를 해결한다면 브루트 포스 알고리즘으로 풀었다고 할 수 있다.

예를 들어, 4자리 숫자로 된 핸드폰의 암호는 0000, 0001, 0002... 9999 까지 총 1만개(104)의 조합 중 하나이므로, 이를 하나씩 대입해 보면 핸드폰의 암호를 통과할 수 있게 된다. 한 번 암호를 입력해 보는데 5초가 걸린다면, 5만 초, 즉 14시간이면 충분하고, 이를 사람 손이 아닌 컴퓨터로 처리할 수 있다면 1초 이내로 찾아낼 수 있게 되는 것이다.

---

하지만 브루트 포스는 자원이 문제, 복잡도에 매우 민감하다는 치명적인 단점을 가지고 있다. (세상의 모든 문제가 브루트 포스로 풀 수 있었으면 효율 좋은 알고리즘 도구도 안 나왔을 것...)

위에서 예시로 들었던 4자리 숫자 핸드폰 암호를 알아보는 시간 복잡도만해도 코드로 짜게 되면
$$
O(n^4)
$$
이 되게 된다. 매우 비효율 적이다. 만약에 자리가 숫자가 아니라 문자였다면 자원의 할당도 엄청 나게 늘어날 것이다.

하지만 브루트 포스 방식으로 써야하는 순간에는 브루트 포스 방식으로 풀어야한다.

문제 해결 방법

1. 주어진 문제를 선형 구조로 구조화 한다.
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
3. 구성된 해를 정리한다.

선형 구조로 구조화 한다는 이야기가 어렵게 들리겠지만, 문제에서 주어진 상황을 컴퓨터가 풀기 쉽게 정리하면 되는 것이다.

가장 유명한 브루트포스 문제인 블랙잭 문제를 보면서 브루트 포스에 대해 이해해 보자.

백준 2798번

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

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

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

        String [] cardList = scan.nextLine().split(" ");

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

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

        int max = 0;
        //3개의 카드를 고르기 때문에 첫 번째 카드는 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보다 클수 없다고 했으니 합이 m보다 작을때만 계산
                    //3카드의 합보다 m이 더 크다면 Max와 sum중에 더 큰 값을 max에 대입
                    //Max는 점점  m값과 가까워 짐
                    if(sum <= m) {
                        max = Math.max(max, sum);
                    }
                    //max == m이면 가장 가까운 합이므로 출력 후 종료
                    if(max == m) {
                        System.out.println(max);
                        return;
                    }
                }
            }
        }
        System.out.println(max);

    }
}

위 문제에서는 3중 for문을 적절히 사용하면 된다.

물론 위의 방법에 더 조건을 걸어주면 더 짧은 시간으로 문제를 해결할 수 있을 것이다.

결국 브루트 포스는 모든 경우의 수를 탐색하는것이 중요하다. 가장 좋은 방법은 모든 경우를 탐색하면서 각 경우에서 쓸데 없는 연산을 하지 않는 것이다.

깃허브포스팅