[알고리즘] C++로 이해하는 브루트포스

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)

---

☑️ C++로 이해하는 부르트포스

부르트포스(Brute Force)는 검색하는 방법 중에서 기초적이고 쉬운 알고리즘이다. 이 알고리즘은 확인이 가능한 모든 경우의 수를 하나씩 확인한다. 선형 검색에서 단순하게 확장한 알고리즘이라서 단순법으로도 부른다. 단어부터 알고리즘의 성격을 볼 수 있는데 Brute는 짐승, Force는 힘을 의미한다. 이 두 단어를 합쳐서 직역하면 짐승같은 힘을 말한다. 무차별적인 힘으로 풀어낸다는 알고리즘의 성격을 그대로 담고 있다.

 

1️⃣ 왜 부르트포스를 사용할까?

부르트포스가 단순하고 직관적이기 때문이다. 시간과 기회가 무한하다고 가정한다면 부르트포스가 풀어내지 못할 문제는 없다. 모든 가능성을 시도하기 때문에 정확한 답을 도출할 수 있다.

 

2️⃣ 어떻게 부르트포스가 동작할까?

부르트포스는 앞서 말한 것 처럼 모든 가능성을 시도한다. 다음은 부르트포스가 동작하는 의사코드와 동작 방식을 담았다.

text = 검색할 문자열 = "ABCDEF"
find = 찾는 단어 = "EF"

1. text의 N번 인덱스 값과 find의 N번 인덱스의 값을 비교한다.
    1-1. (틀릴 경우) text의 N+1번 인덱스 값과 find의 N번 인덱스의 값을 비교한다.
    1-2. (맞을 경우) text의 N+1번 인덱스 값과 find의 N+1번 인덱스의 값을 비교한다.

 

☑️ 부르트포스 구현하기

부르트포스에는 정형화된 코드가 없다. 문제, 상황 등에 맞는 코드를 작성하고 모든 경우의 수를 대입하여 찾는다면 부르트포스다. 아래의 예시 문제를 풀면서 부르트포스를 익혀보자.

 

1️⃣ 셀프 넘버

링크 : https://www.acmicpc.net/problem/4673

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<int> n(10001, 0);
    int x, y, sum;

    for (int i = 1; i < 10001; ++i) {
        n[i] = i;
    }

    for (int i = 1; i < 10001; ++i) {
        sum = i;
        x = i;

        while (x > 0)
        {
            y = x % 10;
            sum += y;
            x = x / 10;
        }

        if (sum < 10001)
            n[sum] = 0;
    }

    for (int i : n)
    {
        if (i != 0)
            cout << i << '\n';
    }

    return 0;
}

 

2️⃣ 분해합

링크 : https://www.acmicpc.net/problem/2231

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    int sum = 0, x, y;
    for (int i = 1; i < n; ++i) {
        sum = i;
        x = i;

        while (x > 0)
        {
            y = x % 10;
            sum += y;
            x = x / 10;
        }

        if (sum == n)
        {
            cout << i;
            return 0;
        }
    }
    cout << 0;

    return 0;
}