[Algorithm] 브루트 포스(Brute Force)

브루트 포스(Brute Force)

개념

• 브루트(Brute)와 포스(Force)가 결합되어 만들어진 단어이며, "난폭한 힘(폭력)" 이라는 뜻이다.
• 문제 해결을 위해 오래 걸리고 자원이 많이 들어서 무식하다고 생각될 수도 있지만, 항상 100%의 정확성을 보인다.
• 정답(Solution)이 발견될 때까지 가능한 모든 선택지를 찾는 방법이다.
  • 예) 4자리 숫자의 패스워드를 찾기 위해 0000부터 9999까지 하나씩 입력하여 찾아보는 경우
  • 따라서 브루트 포스 알고리즘은 완전 탐색 알고리즘이라고 할 수 있다.
• 간단하고 일관적이지만, 매우 느리다는 단점이 있다.
• 거의 완벽하게 병렬 작업이 가능하여 병렬 프로그래밍에서 사용된다.
• 패턴 매칭(Pattern Matching) 등의 작업에 사용될 수 있다.
• 너비 우선 탐색(Breadth First Search; BFS)과 순차 탐색(Sequential Search)과 관련이 깊다.
• 시간 복잡도는 입력값의 크기(Input Size)에 따라 달라진다.

 

문제 해결 방법

• 브루트 포스 알고리즘을 이용하여 문제를 해결하는 방법은 다음과 같다.

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

 

외판원 문제(Traveling Salesman Problem; TSP)

많은 수의 도시가 있고, 한 도시에서 다른 도시로의 여행 경비를 알고 있을 때, 각 도시를 한 번만 방문하고 출발한 도시로 되돌아 오는데 여행 경비가 가장 적게 드는 여행 경로는 무엇인가?

• 브루트 포스 알고리즘과 관련된 유명한 문제이다.
• 브루트 포스 알고리즘을 이용할 경우, 모든 경로를 구한 후, 가장 짧은 경로를 선택하는 방식으로 이 문제를 해결할 수 있다.
• 이 방법은 다른 창의적인 알고리즘을 통해 발견한 가능성이 있는 경로들을 제거할 수 있기 때문에 효율적이지 못하다.

 

예 : 한 외판원이 최소의 예산을 이용하여 9개의 도시를 두루 여행한 뒤 다시 보스턴으로 돌아와야 할 경우

• 9개의 도시들을 순서대로 이동할 수 있는 모든 경우의 수는 $9! = 362,880$ 가지에 해당된다.
• 각 도시를 한 번만 방문하고, 최소의 비용으로 출발한 도시로 돌아오는 경로를 찾아야 한다.

 

Traveling Salesman Problem

 

시간 복잡도

• 브루트 포스 알고리즘은 보통 패턴 매칭(Pattern Matching)에서 사용된다.
• 브루트 포스 알고리즘을 이용하여 크기가 `m` 인 문자열 안에서 크기가 `n`인 문자열을 찾을 경우, 시간 복잡도는 $O(mn)$ 이다.

 

브루트 포스 알고리즘으로 해결할 수 있는 예제들

10의 약수의 합을 구하기

• 10의 약수가 될 수 있는 모든 자연수들을 구조화한다.

$$\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} $$

#include <iostream>
using namespace std;

int n, sum;

int main() {
    n = 10;
    for (int i = 1; i <= 10; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    
    cout << n << "의 약수의 총합 : " << sum << '\n';
    
    return 0;
}

10의 약수의 총합 : 18

 

10원과 50원으로 120원을 지불할 수 있는 모든 방법의 수와 최소 동전의 개수 구하기

• 주어진 동전의 종류가 2가지이므로 2차원 형태로 구조화하여 문제를 해결할 수 있다.
• 행을 50원, 열을 10원으로 생각하고 구조화한다.

$$\begin{bmatrix} 0 & 10 & 20 & 30 & 40 & 50 & 60 & 70 & 80 & 90 & 100 & 110 & 120 \\ 50 & 60 & 70 & 80 & 90 & 100 & 110 & 120 \\ 100 & 110 & 120 \\ 150 \\ \cdots \end{bmatrix}$$

• 위 행렬에서 행렬 `(x, y)` 은 50원 동전 `x` 개, 10원 동전 `y` 개를 지불하는 방법으로 생각할 수 있다.
• 따라서 120원을 지불하는 방법으로는 $(0, 12), (1, 7), (2, 2)$ 의 3가지 방법이 있고, 각 방법을 위해 사용한 동전의 수는 각 행과 열의 합, 즉 `x + y` 인 $\{ 12, 8, 4 \}$ 이다.
• 따라서 120원을 지불할 수 있는 모든 방법의 수는 3, 최소 동전의 개수는 4이다.

#include <iostream>
#include <climits>
using namespace std;

int change, ways, minNum = INT_MAX;

int main() {
    change = 120;
    for (int x = 0; 50 * x <= change; x++) {
        for (int y = 0; 10 * y <= change; y++) {
            if ((50 * x) + (10 * y) == change) {
                ways = ways + 1;
                
                // 최솟값 찾기
                if (minNum > x + y) {
                    minNum = x + y;
                }
            }
        }
    }
    
    cout << "지불할 수 있는 방법의 수 : " << ways << endl;
    cout << "최소 동전의 개수 : " << minNum << endl;
    
    return 0;
}

지불할 수 있는 방법의 수 : 3
최소 동전의 개수 : 4

 

패턴 매칭 

#include <iostream>
using namespace std;

// 문자열이 발견된 위치를 출력한다.
int BruteForce(string search, string pattern) {
    int sLen, pLen, j, k;
    
    sLen = search.size();
    pLen = pattern.size();

    for (int i = 0; i <= sLen - pLen; i++) {
        for (j = 0, k = i; (search[k] == pattern[j]) && (j < pLen); j++, k++);
        if (j == pLen) {
            return i;
        }
    }
    return -1;
}

string searchStr, pattern;
int res;

int main() {
    cout << "문자열 입력 : ";
    getline(cin, searchStr);
    
    cout << "찾을 패턴 입력 : ";
    getline(cin, pattern);
    
    res = BruteForce(searchStr, pattern);
    
    if (res == -1) {
        cout << "패턴을 찾지 못함." << endl;
    }
    else {
        cout << "패턴의 시작 위치 : " << res << endl;
    }
    
    return 0;
}

문자열 입력 : God is Great
찾을 패턴 입력 : Great
패턴의 시작 위치 : 7

 

참고 사이트

• https://www.freecodecamp.org/news/brute-force-algorithms-explained/
• http://www.aistudy.com/problem/traveling_salesman_problem.htm
• https://hcr3066.tistory.com/26

 

관련 문제

• https://dev-astra.tistory.com/235

[BOJ-2798][C++] 블랙잭

• https://dev-astra.tistory.com/236

[BOJ-2231][C++] 분해합

• https://dev-astra.tistory.com/237

[BOJ-7568][C++] 덩치