[자료구조]브루트 포스

브루트 포스는 완전탐색 알고리즘, 모든 경우의 수를 탐색하는 알고리즘을 말합니다. 

(Brute : 짐승, 동물    Force : 힘)

 

다른 명칭으로는 키 전수조사, 무차별 대입 공격이라고도 부릅니다. 과거 1990년대 청와대 해킹 사건 당시에 해당 알고리즘이 사용되었던 적이 있습니다. 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과를 가져오는 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력해줍니다.

 

** 브루트 포스를 간략하게 정리하자면

- 문제를 해결하기 위해 모든 자료를 탐색해야 하기 때문에 특정한 구조를

전체적으로 탐색할 수 있는 방법을 필요로 합니다.

- 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는

모든 영역을 전체적으로 탐색하는 방법입니다.

 

** 브루트 포스 알고리즘 유형

1. for문을 이용한 탐색

2. 백트래킹(Backtracking)을 이용한 탐색

3. 깊이 우선 탐색(DFS, Depth First Search)과

너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구

(너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 백트래킹과 관련이 깊습니다)

 

○ 문제해결 방법

1. 주어진 문제를 선형 구조로 만듭니다.

2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색합니다.

3. 구성된 해를 정리합니다.

 

○ 장점과 단점

*장점

- 완벽하게 병렬작업이 가능합니다. GPU를 사용하거나 여러대의 컴퓨터를 가지고 병렬 작업이 가능합니다.

- 암호학에서도 비밀번호를 뚫기 위한 가장 확실한 방법으로 인정받고 있습니다.

- 아라비안 숫자는 0~9까지의 숫자를 대입하면 되지만 로마자의 경우 경우의 수가 많기 때문에, 특정규칙에 따른 우선순위를 정해서 대입규칙을 정하는데 이 부분에서 브루트 포스가 많이 활용됩니다.

 

*단점

- 복잡도가 높을수록 활용이 어렵습니다.

ex) 요즘 비밀번호들은 모두 특수문자 + 대문자 + 8자리 이상의 조건들을 충족하는 경우가 많은데

      비밀번호를 알아내는 시간이 굉장히 오래걸립니다. 만약 위 조건의 비밀번호를 풀기 위한 텍스트 파일을        만든다고 가정한다면 34^8bit가 되며 용량이 1663GB가 됩니다. 복잡도가 높아지는 만큼 무거워집니다.

 

○ 예제

1) 백준 2798번 - 블랙잭

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

이 문제는 브루트 포스 알고리즘으로 해결하는 대표적인 문제입니다. 블랙잭 규칙은 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임입니다. 자료구조를 선형화시키는 것과 경우의 수를 고려하여 문제를 접근하시면 됩니다.

 

 

첫째줄 : 카드의 개수 N, 카드의 합 M

둘째줄 : N개의 카드 숫자

(출력 : M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력)

 

*문제풀이

브루트 포스를 이용하여 처음부터 가능한 정답을 확인해보자면 이렇습니다.

5 + 6 + 7 = 18

5 + 6 + 8 = 19

5 + 6 + 9 = 20

6 + 7 + 8 = 21

 

정답은 숫자 6, 7, 8인데 해당 케이스 같은 경우 숫자가 딱 떨어지기에 다음 경우의 수를 살펴보지 않아도 되나 그렇지 않은 경우도 존재합니다. 두 번째 케이스를 같이 보시겠습니다.

만약에 두 번째 케이스와 같이 숫자가 비선형적이라면 경우의 수를 끝까지 살펴봐야 겠지만 이 경우 선형적이기 때문에 연속된 세개의 숫자 합이 500이 넘어가게 되면 프로그램을 종료시킬 수 있습니다.

예를 들어 138 + 181 + 185 = 504이기 때문에 이후의 숫자 합은 모두 500이 넘을 것입니다.

만약 비선형적이라면 끝까지 경우의 수를 고려해야 합니다.

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int result = search(arr, N, M);
        System.out.println(result);
    }
 
    // 탐색
    static int search(int[] arr, int N, int M) {
        int result = 0;
 
        // 3개를 고르기 때문에 첫번째 카드는 N - 2 까지만 순회
        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                for (int k = j + 1; k < N; k++) {
                    int temp = arr[i] + arr[j] + arr[k];
 
                    if (M == temp) {
                        return temp;
                    }
 
                    if (result < temp && temp < M) {
                        result = temp;
                    }
                }
            }
        }
        // 모든 순회 종료 후 리턴
        return result;
    }
}
 

 

*참고

https://hyunipad.tistory.com/91