브루트포스 알고리즘 (Brute force 알고리즘)

목차

 

브루트포스란?

  복잡한 알고리즘을 굳이 생각하지않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 다 살펴보는 것을 의미합니다. brute force, BF, 완전탐색(exhaustive search), 완탐 정도로 불립니다.

 

  설명을 위해 코딩테스트와 비슷한 형태의 문제로 예를들겠습니다.

N개의 숫자를 입력받아 이 중 임의의 3개의 수를 골랐을 때, 세 수의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N과 S가 주어진다. (3 ≤ N ≤ 20, lSl ≤ 1,000,000) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초)

 

  예를들어 만약 입력이 아래와 같이 주어졌다면, N=10, S=0이고 3개를 골라 합이 S가 되는 경우는 [1, 2, -3], [3, -2, -1], [10, 11. -21]의 3가지가 있으므로 '3'을 출력해주면 됩니다.

10 0
1 2 3 -3 -2 -1 10 11 -21 40

 

  이 문제를 어떻게 풀 수 있을까요? 복잡하게 생각할 것 없이 모든 경우의 수를 살펴보는 방법을 생각해보겠습니다. 우선 모든 경우를 판단했을 때 적당한 시간 내에 프로그램이 돌아갈지 확인하겠습니다.

 

  n개의 숫자 중 3개를 순서와 상관없이 고르면 되므로, 조합(combination) nCr에서 r이 3인 경우를 구하면 됩니다. 위의 경우 괄호안에 제시된 조건 내에서 최악의 경우는 N=20인 경우입니다. 이 때, 20개 중 3개를 구하면 되므로 20x19x18 / (3x2) = 1140가지 입니다. 컴퓨터는 물론 사양마다 다르지만 보통 대강 시간을 따질 때 1억번의 단순 연산(덧셈, 뺄셈 곱셈 같은..)을 1초정도로 잡으므로 1140번은 사람에겐 모든 경우를 보자면 몇일 걸리겠지만, 컴퓨터는 0.1초도 안걸리는 쉬운 연산입니다.

  위와 같이 시간이 얼마나 걸릴 지 생각해보는건 '시간 복잡도'를 생각해보는 겁니다. 시간 복잡도에 대해서는 '알고리즘 시간복잡도에 대해' 글에 더 자세히 써져 있습니다. 시간 복잡도 개념을 이해하는건 실무에서도 중요합니다. 실무에서의 예시는 '자바에서 문자열 합칠 때 '+' 연산을 쓰지 마세요!' 글에 나와 있습니다.

 

  그럼 구현을 해보겠습니다. N과 S를 입력받는건 숫자니까 int로 받으면 되겠고.. 미리 정해지지 않은 N개의 숫자를 받아둬야 하니 하나하나 변수를 두고 입력받는 것 보다는 그때그때 크기를 조정할 수 있는 배열이나 리스트로 받으면 좋겠습니다. 위의 경우 데이터를 삭제할 일이 없고 대신 임의의 위치의 숫자를 계속 살펴봐야 하니 리스트보다는 배열이 좋겠네요. 3개의 수를 고를 수 있는 모든 경우를 봐야하니 반복문 3개를 중첩해서 사용하면 되겠습니다. 그럼 자바로 짜보면 아래와 같습니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] input = new int[n];
        for (int i = 0; i < input.length; i++) {
            input[i] = sc.nextInt();
        }

        // solve
        int resultCnt = 0;
        for (int i = 0; i < input.length; i++) {
            for (int j = i+1; j < input.length; j++) {
                for (int k = j+1; k < input.length; k++) {
                    int sum = input[i] + input[j] + input[k];
                    if (sum == s) {
                        resultCnt++;
                    }
                }
            }
        }
        System.out.println(resultCnt);
    }
}

 

  위와 같이 최악의 경우라도 모든 경우를 컴퓨터로 살펴보기에 문제가 없다면 단순히 모든 경우를 살펴보면 됩니다. 단순히 모든 경우를 보는것도 하나의 알고리즘이라 할 수 있습니다. 결국 알고리즘으로 치자면 가장 쉬운 알고리즘이나, 활용 방법에 따라 최고의 효율을 보여줄 수 있는게 brute force 입니다. 컴퓨터로 어차피 적정한 시간내에 처리될 만한 수준의 데이터라면, 복잡하게 시간들여 생각할 것 없이 그냥 다 보면 되니까요!

 

 

재귀 함수를 익히면 브루트포스를 짜기 수월합니다.

  위 문제를 조금만 변형하여 좀 더 생각해보겠습니다.

N개의 숫자를 입력받아 이 중 임의의 R개의 수를 골랐을 때, 고른
R개의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N, R, S가 주어진다. (R ≤ N ≤ 20, lSl ≤ 1,000,000. 2 ≤ R ≤ 7) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초)

 

  이번엔 3개를 고르는게 아니고, R개를 고르는 것으로 변경되었습니다. 최악의 경우 nPr에서 n은 20, r은 7일 때이므로 27,907,200개의 경우만 보면 되므로 사람이 직접 모든 경우를 본다면 몇달이 걸리겠지만, 역시 컴퓨터로써는 1초도 걸리지 않는 쉬운 연산입니다. 그런데 짜려고 보니 3개에서 R개를 고르는 것으로만 변경되었는데 난이도가 엄청나게 올라갔습니다. 어쨌든 한번 짜보겠습니다.

 

  처음에 제시된 문제는 3개를 살펴보니 3중첩 반복문을 사용해 해결했습니다. 이번엔 R개를 살펴봐야하니, 최대 7중첩 반복문이 필요하고, R 값이 따라 반복문의 수가 변경되야할 것같습니다. 어.. 노가다지만 한번 해보죠!

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
                int s = sc.nextInt();
        int[] input = new int[n];
        for (int i = 0; i < input.length; i++) {
            input[i] = sc.nextInt();
        }

        // solve
        int resultCnt = 0;
        switch (r) {
            case 2 :
                for (int i = 0; i < input.length; i++) {
                    for (int j = i+1; j < input.length; j++) {
                        int sum = input[i] + input[j];
                        if (sum == s) {
                            resultCnt++;
                        }
                    }
                }
                break;
            case 3 :
                for (int i = 0; i < input.length; i++) {
                    for (int j = i+1; j < input.length; j++) {
                        for (int k = j+1; k < input.length; k++) {
                            int sum = input[i] + input[j] + input[k];
                            if (sum == s) {
                                resultCnt++;
                            }
                        }
                    }
                }
                break;
            case 4 :
                for (int i = 0; i < input.length; i++) {
                    for (int j = i+1; j < input.length; j++) {
                        for (int k = j+1; k < input.length; k++) {
                            for (int x = k+1; x < input.length; x++) {
                                int sum = input[i] + input[j] + input[k] + input[x];
                                if (sum == s) {
                                    resultCnt++;
                                }
                            }
                        }
                    }
                }
                break;
            case 5 :
                .... (5중첩 반복문)
                break;
            case 6 :
                (무언가 6중첩 반복문)
                break;
            case 7 :
                (말하기도 민망한 7중첩 반복문)
                break;
        }
        System.out.println(resultCnt);
    }
}

 

  case 5부터 이건 사람이 할짓이 아니란걸 깨달았습니다. 이젠 i, j, k 말고 무슨 변수명을 쓸지도 고민됩니다. 6개일때랑 7개일때도 해야됩니다! 심지어 R이 이문제에선 7까지였지만 100까지 가능하면 어쩔껍니까!

 

  위와 같은 이유와, 반복문이 여러개면 코드를 보는것도 힘들다는 이유 등이 합쳐져서, 보통 모든 경우를 탐색할 경우 재귀함수를 사용하는게 편한 경우가 많습니다. 물론 재귀함수를 현업 일에 쓸 일 자체가 거의 없고, 일반적으로 이후 유지보수를 할 경우 유지보수를 다른사람이 한다면 그 사람이 재귀함수를 이해할 수 있을지 없을지도 모르며, 설계를 잘못하면 메모리 누수로 이어지기 때문에 현업 코드에서는 재귀함수를 잘 쓰지 않습니다. 하지만 안쓰는것과 못쓰는건 다릅니다.

 

  재귀함수(=recursive function =재귀호출 =recursion)는 특히 동일한 코드를 반복하는 위와 같은 반복문을 간단하게 구현할 때 유용합니다. 재귀함수는 일반적으로는 큰 덩어리를 비슷한 형태의 좀 더 작은 조각으로 나누어서 동작시키고, 그걸 더 작은 동작으로 나누고.. 가장 작은 덩어리에서 결과를 내서 다시 큰 덩어리쪽으로 결과를 리턴하며 결과를 합쳐 최종적으로 큰 덩어리를 해결하는 겁니다. 중요한건 더이상 나누어지지 않는 기저 조건(base case)을 잘 설정해야 무한루프로 빠지지 않습니다.

 

  사실 재귀함수는 일반적으로 코드를 쭉~따라서 읽기 같은 방법으로 따라가며 살펴보기 어려워서, 이해하는것 자체가 어렵습니다. 처음 봤을 때 어려운게 정상이니 걱정 마세요. 다들 그래요.

 

  그럼 재귀함수를 활용해서 문제를 풀어보겠습니다.

import java.util.Scanner;

public class Main {
    private static int resultCnt = 0;
    private static int[] input;
    private static int n, r, s;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        s = sc.nextInt();
        input = new int[n];
        for (int i = 0; i < input.length; i++) {
            input[i] = sc.nextInt();
        }
        solve(-1, 0, 0);
        System.out.println(resultCnt);
    }

    private static void solve(int idx, int sum, int cnt) {
        // base case
        if (cnt == r) {
            if (sum == s) {
                resultCnt++;
            }
            return;
        }

        // recursion
        for (int i = idx+1; i < n; i++) {
            sum += input[i];
            solve(i, sum, cnt+1);
            sum -= input[i];
        }
    }
}

 

  이전 복잡했던 반복문의 중첩이 간단하게 재귀함수로 합쳐졌습니다. 위의 경우 단순히 보기엔 로직을 이해하기 힘들 수 있으나, 직접 그려보면서 이해해보시면 이해가 되실껍니다. solve 함수를 말로 풀어보면 다음과 같이 동작합니다.

• 우선 base case를 살펴봅니다. 처음 cnt는 0이고, r은 최소 2이니 base case에 들어가지 않습니다.
• 맨 처음 main함수에서 solve 함수를 호출할 때 idx가 -1로 들어오고, i는 idx+1에서 시작하니 0부터 시작합니다.
• 0이었던 sum에 input배열의 0번 idx 값을 더합니다.
• solve함수에 현재 idx인 i를 넣고, '2'에서 합친 sum을 넣고, cnt를 1 증가시켜줍니다.
• 다시 solve 함수가 실행되고 현재 cnt는 1 입니다. 역시 base case에 충족되지 않으니 다음으로 넘어갑니다.
• 이번엔 i가 1부터 시작됩니다. (이전 복잡했던 반복문에서 i=0, j=i+1, ...로 진행한것과 마찬가지 동작) sum에 input[1]을 더해주고 다시 solve 함수로 들어갑니다.
• ...... 진행하다보니 base case를 충족하는 경우가 발생했습니다. 즉, 문제에서 제시된 R번만큼 숫자를 더했습니다. 그렇다면 이제 현재까지의 sum을 보고 S와 비교합니다. 같다면 resultCnt를 1 증가하고 종료합니다. 같지 않더라도 종료합니다. (이와 같이 재귀 함수에는 어떠한 경우에도 재귀함수가 무한으로 호출되지 않도록 종료시켜주는 base case가 반드시 필요합니다. 이걸 제대로 설정하지 못하면 메모리 누수. 스택 오버플로우 등의 문제가 발생하게 됩니다.)
• '7'에 해당하는 solve 함수를 호출했던 solve함수의 for문으로 다시 돌아옵니다. 그럼 '7'에 해당하는 solve함수로 들어가기 전 더해뒀던 input[어딘가]의 값을 다시 빼줍니다. for문의 다음 loop에 영향을 끼치면 안되니까요.
• ... 반복

 

 

생각에 따라 '완전' 탐색의 범위는 달라질 수 있습니다.

  모든 경우를 살펴보는게 브루트포스 입니다. 하지만 '모든 경우'라는 부분은 약간의 아이디어를 추가해서 줄일 수 있는 경우가 많습니다. 예를들어 백준 3040 문제를 생각해보죠.

 

  위 문제는 9개의 숫자가 주어질 때, 이 중 7개를 골라 합이 100이 되는 경우를 찾으라는 문제입니다.

단순히 생각해보면 위에 제가 적어둔 문제에서 N=9, R=7, S=100 인 경우와 같습니다. 그럼 7중 반복문이나 재귀함수로 풀 수 있겠네요!

 

  근데 더 간단한 방법이 있습니다. 9개의 합을 미리 구해두고, 이 중 2개를 골라 '합 - 고른 2개의 합'이 100이 되는걸 찾으면 됩니다. 즉, 7중 반복분이 이중 반복문으로 줄어들었습니다. 게다가 후자도 역시 '완전' 탐색입니다. 이처럼 생각을 어떤식으로 하냐에 따라 '모든 경우'는 달라질 수 있습니다.