[알고리즘] 완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm

 

완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm

Brute : 무식한

Force : 힘

 

직역하면, 무식한 힘을 갖는 알고리즘이란 뜻으로, 완전 탐색 알고리즘의 한 종류이지만 완전 탐색의 또 다른 이름으로 쓰이기도 한다. 브루트 포스 알고리즘은 완전탐색으로 답을 도출하는 알고리즘이며, 대부분은 반복문과 조건문을 통하여 답을 도출한다.

 

모든 경우의 수를 전부 탐색하기 때문에, 100%의 정확성을 보장하지만,

모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다.

 

---

완전 탐색과 브루트포스 알고리즘의 차이

브루트 포스와 완전탐색은 의미차이가 거의 없기 때문에, 같은 의미로 쓰이기도 한다. 영어로도 완전탐색은 Exhaustive Search 라고도 하고, Brute Force Search 라고도 한다.

 

하지만, 이 둘은 아주 작은 차이가 있다.

 

먼저, 완전 탐색 알고리즘은 모든 경우의 수를 전부 탐색하는 방식의 알고리즘을 칭하며, 그 결과를 찾는 것보다 탐색한다는 과정에 중점을 둔다.

 

하지만, 브루트포스 알고리즘은 문제를 해결 하기 위하여, 모든 경우를 탐색하고 답을 도출하는 알고리즘으로, 결과를 찾는 것에 중점을 둔다.

 

즉, 주 된 목적이 탐색과정이냐, 답을 도출하는 것이냐의 차이가 있는 것이다.

 

 

---

브루트포스 알고리즘의 사용 조건

1. 문제에서 달성하고자 하는 솔루션이 잘 정의 되어 있어야한다.

솔루션이 잘 정의되어 있지 않은 문제라면, 브루트 포스를 사용한 솔루션이 올바른지의 여부를 확인할 수 없다.

 

2. 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

문제에서 고려해야할 솔루션의 수가 한정되어 있어야 한다. 고려해야할 솔루션의 수가 무한하거나 너무 크면 브루트포스 알고리즘은 효율적이지 않은 방법이다.

 

 

---

브루트포스 알고리즘 예시

 

1. 반복문을 사용하는 경우

브루트포스 알고리즘은 대부분 반복문과 조건문을 활용해서 모든 경우를 탐색한다.

 

예로, 왼쪽 그림과 같은 일상생활에서 자주 볼 수 있는 숫자형 자물쇠를 보자.

 

비밀번호를 잊어버렸다면, 000 부터 999까지 하나씩 돌리는 방식으로 비밀번호를 구할 수 있고, 자물쇠가 풀렸다면, 더는 돌릴 필요가 없다.

 

 

이를 코드로 나타내면 아래와 같다.

public class example {

    static int [] password = {3,4,5};

    public static void main(String[] args) {

        for(int i = 0 ; i < 10 ; i ++){
            for(int j = 0 ; j < 10 ; j ++){
                for(int k = 0 ; k < 10 ; k ++){

                    if(password[0] == i && password[1] == j && password[2] == k){

                        System.out.println("자물쇠 해제 ");
                        System.out.println("비밀번호는 " + i + j + k);
                        break;
                    }

                }
            }
        }
    }
}

 

 

 

2. 재귀를 사용하는 경우

간단하게 10 팩토리얼을 구하는 문제가 있다고 하자.

 

10팩토리얼은 1 * 2 * 3 * ... 중략 ... * 8 * 9 * 10 이므로, 10까지의 모든 숫자를 곱해주어야 한다.

반복문을 통하여 해결할 수도 있지만, 재귀를 통하여 아래의 코드처럼 해결할 수 있다.

public class example {

    public static void main(String[] args) {
        System.out.println( "10 factorial = " + factorial(10));

    }

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

 

 

 

 

또 다른 재귀 예시

피보나치 수열의 10번째 숫자를 구하는 문제가 있다고 하자.

 

피보나치 수열은 f(n) = f(n-1) + f(n-2)의 점화식을 가지고, 10번째 숫자를 구하기 위해서는 처음부터 10번째까지의 계산이 필요하게된다.

public class example {

    public static void main(String[] args) {

        System.out.println("fibonacci의 10번째 수는 " + fibonacci(10));
    }

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

 

 

피보나치 수열의 경우, 모든 경우를 탐색하는 브루트포스를 이용하여 해결이 가능하기는 하지만,

DP (다이나믹 프로그래밍, 동적계획법)를 사용하여 계산할때, 중복된 계산을 피할 수 있으므로 더욱 효율적인 계산이 된다.

 

따라서 브루트 포스를 사용하는 것은 항상 효율적이지는 못하며, 더 효율적이 방법이 없는 지 고민해보고 사용하여야 한다.