[Algorithm] 브루트 포스(Brute Force) 알고리즘이란- 개념, 특징, 구현방법

 

브루트 포스 (Brute Force)

브루트(Brute)는 '무식한'을 뜻하고, 포스(Force)는 '힘'을 뜻한다.

즉, '발생가능한 모든 경우를 탐색하는 무식한 방법'을 말한다.

 

 

정의

• 모든 영역을 전체 탐색(완전 탐색)하는 방법이다.
• 전체 탐색이므로 해만 존재한다면, 반드시 찾을 수 있다.
• 전체 탐색하는 방법으로 문제를 해결한다면 브루토 포스 알고리즘으로 문제를 해결한 것이다.
  • 순차탐색 : 선형 구조(ex-배열)를 전체적으로 탐색
  • 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) : 비선형 구조를 전체적으로 탐색

전체 탐색(완전 탐색)

 

모든 경우의 수를 탐색하는 알고리즘이다.

 

장점

• 알고리즘 설계와 구현이 쉽다.
• 복잡한 알고리즘 없이 빠르게 구현가능하다.
• 입력 값이 작은 경우 유용하다.

 

단점

• 복잡도에 매우 민감하다
• 실행 시간이 오래 걸린다.
• 메모리 효율면에서 매우 비효율적이다.
• 즉, 매우 비효율적이다

 

 

방법 1 : 순열(permutation)

• 서로 다른 N개의 원소에서 r(≤N)개를 뽑아 순서대로 나열하는 경우의 수
• 이 때, 총 경우의 수는 N!이다.
• 순서가 중요한 경우에 주로 사용한다.
• 특정 순열의 다음순열 또는 이전순열을 구하는 경우에 사용한다.

 

 

최초순열/최종순열

순열의 다음순열과 이전 순열을 구하는 방법에 대해 알기 위해서는 먼저 최초/최종 순열에 대해 이해해야 한다.

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

▶ 최초 순열 :  오름차순 순열

▶ 최종 순열 : 내림차순 순열

 

i번째 기준 i+1번째부터 내림차순이라면 최종 순열이 된다. 이후에는 i번째부터 모두 오름차순인 최초순열이 된다.

 

 

즉, 특정 순열의 다음 순열은 아래의 순서에 따라 구할 수 있다.

위의 순열들 중 {1,3,2}의 다음 순열을 구하면서 이해해보자.

1. 먼저, i-1까지는 고정으로 변동이 없다.

• {1, 3, 2}에서 1번째부터 내림차순이므로 i는 0이다. 따라서 변동이 없는 숫자는 없다.

 

2. i+1번째부터의 숫자 중 자신보다 큰 숫자를 찾는다.

• 1번째부터의 숫자 중 자기자신 0번째 숫자(=1)보다 큰 숫자는 3, 2이다.

 

3. 2의 숫자들 중 가장 작은 숫자를 구해, swap한다.

• 3, 2 중 가장 작은 숫자는 2이므로, 1과 2를 swap한다.
• 결과는 {2, 3, 1}이다.

 

4. i+1째부터의 숫자를 오름차순으로 나열한다.

• 1번째부터의 숫자를 오름차순으로 나열하면 {2, 1, 3}이 된다.

 

 

 

다음 순열을 구하는 로직

 

위의 규칙을 로직으로 구현하면 다음과 같다.

예) A = {7, 2, 3, 6, 5, 4, 1}

 

1. A[i-1] ≤ A[i]를 만족하는 i 값 중 가장 큰 값을 찾는다(뒤에서부터 찾는 경우, A[i-1] ≥ A[i] 중 가장 작은 i 값을 찾는다).

• 현재 i 값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 것이다.
• 현재 기준에서 최종 순열을 찾는다.
• 예에서 i = 3

 

2. j ≥ i 중, A[j] > A[i-1]을 만족하는 j 값 중 가장 큰 값을 찾는다.

• 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾는다.
• 예에서 i-1번째 수는 3이므로, 3보다 큰 숫자 중 인덱스 값이 가장 큰 경우(j)는 4이다.

 

3. A[I-1]과 A[j]를 swap한다.

• 2번째 숫자 3과 5번째 숫자 4를 swap한다.

 

4. i 이후의 순열을 모두 뒤집는다.

• 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다.
• 최종 결과는 A = {7, 2, 4, 1, 3, 5, 6}

 

 

브루트 포스 - 순열 예제

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

2529번: 부등호

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String[] sign = new String[k];
        int[] result = new int[k+1];
        String max_result = "";
        String min_result = "";

        for(int i=0; i<k; i++){
            sign[i] = sc.next();
        }

        //큰 수 찾기
        for(int i = 9; i>=9-k; i--){
            result[9-i] = i;
        }


        while(true){
            if(check(result, sign)) break;
            prev_perm(k, result);
        }

        //큰 수 출력
        for(int i = k; i>=0; i--){
            max_result = max_result.concat(Integer.toString(result[k-i]));
        }

        //작은 수 찾기
        for(int i = 0; i<=k; i++){
            result[i] = i;
        }

        while(true){
            if(check(result, sign)) break;
            next_perm(k, result);
        }

        for(int i = k; i>=0; i--){
            min_result = min_result.concat(Integer.toString(result[k-i]));
        }

        System.out.println(max_result);
        System.out.println(min_result);
    }

    private static void prev_perm(int k, int[] max){

        int i = k;
        
        //k에서부터 내림차순이 아닌 경우를 찾는다(최초순열)
        while(i>0 && max[i-1]<=max[i])
            i--;

		//순열 자체가 최초 순열일 경우, return한다
        if(i<=0) return;

		//i-1번째 수보다 크거나 같은 수 중 j값이 가장 작은 경우를 선택한다
        int j = k;
        while(max[j] >=max[i-1])
            j--;

		//i-1번째 수와 j번째 수를 바꾼다
        change(i-1, j, max);
        
        //i~k사이의 모든 수를 뒤집는다
        j = k;
        while(i<j){
            change(i, j, max);
            i++;
            j--;
        }
    }

    private static void next_perm(int k, int[] min){

        int i = k;
        
        //k에서부터 오름차순이 아닌 경우를 찾는다(최종순열)
        while(i>0 && min[i-1]>=min[i])
            i--;

		//순열 자체가 최종 순열일 경우, return한다
        if(i<=0) return;

		//i-1번째 수보다 같거나 작은 수 중 j값이 가장 작은 경우를 선택한다 
        int j = k;
        while(min[j] <= min[i-1])
            j--;

		//i-1번째 수와 j번째 수를 바꾼다
        change(i-1, j, min);
        
        //i~k사이의 모든 수를 뒤집는다
        j = k;
        while(i<j){
            change(i, j, min);
            i++;
            j--;
        }
    }

    private static boolean check(int[] arr, String[] sign){
        for(int i = 0; i<arr.length-1; i++){
            if(sign[i].equals("<") && arr[i]>=arr[i+1]) return false;
            if(sign[i].equals(">") && arr[i] <= arr[i+1]) return false;
        }
        return true;
    }

	//i번째 숫자와 j번째 숫자 교환
    private static void change(int i, int j, int[] result){ 
        int tmp = result[i];
        result[i] = result[j];
        result[j] = tmp;
    }
}

 

 

 

 

 

방법 2 : 재귀(recursion)

• 자기 자신을 호출하는 함수이다.
• 동일한 코드를 반복하는 반복문을 간단하게 구현할 때 유용하다.

 

재귀함수 사용 시 주의할 점

1. 재귀를 탈출하기 위한 탈출 조건이 필요하다.

• 탈출 조건이 없다면 무한 루프가 발생할 수 있다.

2. 현재 함수의 상태를 저장하기 위한 parameter가 필요하다.

• 현재 함수 상태를 저장할 수 없다면 재귀 탈출 조건을 만들 수 없게 될 수 있다.

3. return문을 통해 필요한 값을 반환한다.

• 필요에 맞게 return을 정의해야만 한다.

 

 

브루트 포스 - 재귀 예제

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

6603번: 로또

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

public class Main {

	//재귀 함수
    private static void recursion(ArrayList<Integer> testCase, boolean[] visited, int index, int n, int r){
        
        //재귀 탈출 조건
        if(r==0) {
            for(int i = 0; i<n; i++){
                if(visited[i]) System.out.print(testCase.get(i) + " ");
            }
            System.out.println();
            return;
        }

        if(index == n) return;

		//true일 때
        visited[index] = true;
        recursion(testCase, visited, index+1, n, r-1);

		//false일 때
        visited[index] = false;
        recursion(testCase, visited, index+1, n, r);
    }
    public static void main(String[] args){
        List<ArrayList<Integer>> testCases = new ArrayList<>();
        Scanner sc = new Scanner(System.in);

        while(true){
            int k = sc.nextInt();

            if(k==0) break;

            ArrayList<Integer> testCase = new ArrayList<>();
            for(int i = 0; i<k; i++){
                int s = sc.nextInt();
                testCase.add(s);
            }
            testCases.add(testCase);
        }

		//모든 단어에 대해 수행
        for(ArrayList<Integer> testCase : testCases){
            List<Integer> result = new ArrayList<>();
            boolean[] visited = new boolean[testCase.size()];
            recursion(testCase, visited, 0, testCase.size(), 6);
            System.out.println();
        }

    }
}

 

 

 

 

문제 해결 방법 (선형구조일 때)

1. 주어진 자료를 선형 구조로 구조화한다.
2. 구조화된 자료들을 적절한 방법으로 해를 구할 때까지 순차 탐색한다.
3. 탐색한 해를 정리한다.

 

 

 

 

 

참고자료
https://hongjw1938.tistory.com/78
https://hcr3066.tistory.com/26