브루트 포스(Brute-Force)

컴퓨터의 가장 큰 장점이 무엇일까? 바로 연산 속도가 사람에 비해 훨씬 빠르다는 것이다. 브루트 포스(Brute-Force)는 컴퓨터의 이러한 특성을 이용하여 가능한 모든 답을 고려해보고, 그 중 정답을 찾아내는 문제 해결 기법이다.

 

브루트 포스는 거의 모든 문제를 해결하는 데 사용할 수 있지만 가능한 답의 개수와 실행 시간이 비례하기 때문에 가능한 답의 개수를 계산해보고 시간 제한 안에 계산할 수 있는 범위인지 확인한 다음에 사용해야 한다.

 

이 문제를 보면 두 수 $a, b$의 최대공약수와 최소공배수를 찾아야 한다. 최대공약수는 항상 $\text{min}(a,b)$보다 같거나 작고, 최소공배수는 항상 $ab$보다 같거나 작기 때문에 $1$부터 답이 될 수 있는 수까지 순회하면서 찾으면 된다. 이 경우에 시간 복잡도는 $O(ab)$가 되고, $ab \leq 10^6$이기 때문에 시간 내에 통과할 수 있다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int t; cin >> t;

    while (t--) {
        int a, b; cin >> a >> b;
        if (a > b) swap(a, b);
        int gcd, lcm;

        for (int g = a; g > 0; g--) {
            if (a % g == 0 && b % g == 0) {
                gcd = g;
                break;
            }
        }

        for (int l = b; l <= a * b; l++) {
            if (l % a == 0 && l % b == 0) {
                lcm = l;
                break;
            }
        }

        cout << lcm << ' ' << gcd << '\n';
    }
}

 

반면 브루트 포스가 시간 내에 풀 수 없는 문제도 굉장히 많다. 이 문제는 위와 같이 최소공배수를 구하는 문제다. 하지만 $ab$가 최대 $45000^2 \fallingdotseq 2\times 10^9$이기 때문에 시간 내에 통과할 수 없다. 이러한 문제들은 다른 알고리즘(이 문제의 경우에는 유클리드 호제법)을 사용해야 한다.

 

문제를 처음 보았을 때 항상 브루트 포스로 풀리는지 한번 확인하고 넘어가는 것이 좋다. 브루트 포스로 간단하게 풀 수 있는 문제를 괜히 어려운 풀이를 생각해서 힘들게 풀 수도 있기 때문이다.