완전 탐색, 브루트 포스란?

Brute Force의 사전적 의미를 보면 다음과 같다.

brute: 무식한 + force: 힘

무식한 힘으로 해석할 수 있다.

즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

장점

알고리즘을 설계하고 구현하기 쉽다.
복잡한 알고리즘 없이 빠르게 구현할 수 있다.

단점

알고리즘 실행 시간이 매우 오래 걸린다.
메모리 효율 쪽으로 매우 비효율적이다.

종류

브루트 포스는 기본 구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다.

선형 구조 : 순차 탐색
비선형 구조 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)
- 심화 : 백트래킹(재귀)

백트래킹과 DFS, BFS에 대해서는 나중에 그래프 탐색 알고리즘과 관련이 있으므로 여기서는 순차 탐색만 파악해보도록 하겠다.

컴퓨터는 약 1초에 1억번(10^8)의 연산이 가능하다고 알려져있는데,

브루트포스는 전체 탐색하기 때문에 좋은 알고리즘 방식이 아니다.

(600억을 확인한다면... 600초 = 확인하는데만 10분...)

그래서 실제 알고리즘을 풀땐, 이 문제가 브루트포스로 가능한지 확인 후

불가능하다면 어떤 알고리즘을 적용해서 시간복잡도를 줄일지 확인해야한다.(DP,누적합,이분탐색 등등)

예시

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

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

위에서 예시로 들었던 4자리 숫자 핸드폰 암호를 알아보는 시간 복잡도만 해도 코드로 짜게 되면

O(n^4)

이 되게 된다. 매우 비효율 적이다. 만약에 자리가 숫자가 아니라 문자였다면 자원의 할당도 엄청 나게 늘어날 것이다.

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

문제 해결 방법

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

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

예제 및 알고리즘

1. 10의 약수의 합을 구하기

10의 약수가 될 수 있는 모든 자연수를 구조화 하자.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 자료를 선형으로 구성하였다.

구조화된 자료가 선형 구조이므로 순차 탐색을 활용하여 첫 번째 원소부터 마지막 원소까지 탐색한다.

탐색하면서 10의 약수가 되는 값만 남겨두고 10의 약수가 될 수 없는 값을 배제한다.

10의 약수는 10을 현재 원소로 나누어떨어지면 그 원소는 10의 약수이다.

위의 과정을 거치면 집합은 다음과 같이 정리된다.

{1, 2, 5, 10}

마지막으로 탐색결과를 정리하여 최종 해를 구한다.

1 + 2 + 5 + 10 = 18

위 문제를 표현해보자.

1
2
3
4
5
6
7

int sum = 0;
for(int i = 1; i <= n; i = i + 1) }
    if(n % i == 0) {
        sum = sum + i;
    }
}
 
Colored by Color Scripter

cs

2. 거스름돈을 지불할 수 있는 방법의 수와 최소 동전의 개수 구하기

10원과 50원으로 120원을 지불할 수 있는 모든 방법의 수와 최소 동전의 개수를 구해보자.

주어진 동전의 종류가 2가지이므로 2차원 즉 행렬의 형태로 구조화하여 일반적 방법으로 해결할 수 있다.

행을 50원, 열을 10원으로 생각하고 구조화해보자.

행렬

위 행렬에서 행렬(0, 0)은 50원 동전 0개, 10원 동전은 0개를 지불하는 방법으로 생각할 수 있다.

따라서 행렬(1, 7)은 50원 동전 1개, 10원 동전 7개로 120원을 지불하는 방법이 된다.

구조화하고 행렬을 2차원으로 탐색하여 120을 이루는 모든 경우의 수를 조사하여, 구한 값들 중 행의 값 + 열의 값의 합의 최소값을 찾으면 최소 동전의 수가 된다.

위 행렬을 탐색해 보면 120원을 지불할 수 있는 경우의 수는 (0, 12), (1, 7), (2, 2)의 3가지이며, 이들의 사용한 동전의 수는 각 행과 열의 합이다. 따라서 사용한 최소 동전의 수는 이 값들 중 최소값이므로 4이다.

120원을 지불할 수 있는 모든 경우의 수 : 3가지, 최소 지불 동전의 수 : 4개

위 문제를 표현해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 
int change = 120;
int ways = 0
int min = INF;
 
for(i = 0; i * 50 <= change; i = i + 1) {
  for(j = 0; j * 10 <= change; j = j + 1) {
     if( (i * 50) + (j * 10) = change) {
        ways = ways + 1;
        if(min > i+j)
           min = i+j;
     }
  }
}
 
Colored by Color Scripter

cs