브루트포스 알고리즘

브루트포스(Brute Force)는 가능한 모든 경우의 수를 전부 시도해 정답을 찾는 완전 탐색 기법이다. 이 방법은 무식해 보이지만, 문제 규모가 작다면 가볍게 시도해볼 수 있는 간단하고 확실한 방식이다.

1. 브루트포스란?

브루트포스는 무조건 모든 경우의 수를 살펴본다. 그러다가 답이 될 만한 조합이나 조건을 만났을 때 결과를 기록한다.

장점: 간단하게 구현 가능하고, 100% 정답을 보장한다.
단점: 경우의 수가 기하급수적으로 늘어나면 시간 복잡도가 커진다.

예를 들어, 블랙잭 문제에서 카드를 3장 뽑아 합이 M을 넘지 않으면서 가장 가깝게 만드는 경우를 생각한다면, 단순하게 모든 3장 조합을 확인해보면 된다.

2. 브루트포스 접근 방식

전체 조합 생성: N장의 카드 중 3장을 뽑는 경우를 전부 만든다.
조건 검사: 각 조합의 합이 M을 넘지 않는지 확인한다.
최적값 갱신: 조건을 만족하면, 기존 결과보다 더 큰지 비교해 최댓값을 갱신한다.

문제가 “카드를 3장 뽑을 때, 합이 M을 넘지 않으며 최대값”이라면 이 순서를 그대로 수행하면 된다.

3. 간단 예시 코드

아래 코드는 약수의 합을 구하는 간단한 브루트포스 예시이다.

public class BruteForceExample {
    public static void main(String[] args) {
        int n = 10;
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            if (n % i == 0) { // i가 n의 약수인지 확인
                sum += i;
            }
        }
        System.out.println("Sum of divisors: " + sum); // 출력: 18
    }
}

로직

1부터 10까지 전부 확인한다.
10으로 나누어 떨어지는 숫자(1, 2, 5, 10)을 찾아서 합산한다.
이렇게 모든 경우를 무작정 확인하는 방식이 브루트포스의 핵심이다.

4. 좀 더 복잡한 예시: 블랙잭

카드가 5, 6, 7, 8, 9처럼 주어졌다고 해보자. 카드를 3장 뽑아 합이 M(21)을 초과하지 않는 최대값을 찾으려고 한다. 모든 i, j, k 조합을 전부 확인해보면 된다.

public class Blackjack {
    public static void main(String[] args) {
        int[] cards = {5, 6, 7, 8, 9};
        int M = 21;
        int result = 0;

        for (int i = 0; i < cards.length; i++) {
            for (int j = i + 1; j < cards.length; j++) {
                for (int k = j + 1; k < cards.length; k++) {
                    int sum = cards[i] + cards[j] + cards[k];
                    if (sum <= M && sum > result) {
                        result = sum;
                    }
                }
            }
        }

        System.out.println("최대 합: " + result); // 출력: 21
    }
}

카드 조합이 여러 가지여도, 전부 시도해보면 된다.
이렇게 무작정 모든 경우를 시도하는 것이 브루트포스의 본질이다.

5. 브루트포스를 언제 사용할까

문제 규모가 작을 때

예: \(N^100\) 정도면 조합을 모두 찾아보는 것도 괜찮다.

정답을 확실히 구하고 싶을 때

모든 경우를 확인하기 때문에 오답이 나올 확률이 거의 없다.

복잡한 알고리즘을 설계하기 전

먼저 브루트포스로 틀을 짜보고, 정답이 나오는지 확인한 뒤, 더 효율적인 방법으로 개선한다.
브루트포스 좋은 백업 솔루션이 될 수 있다.

6. 마무리

브루트포스는 문제가 작은 경우에 활용하기 좋은, 무식하지만 확실한 알고리즘이다. “모든 경우”를 시도하므로, 정확성은 100%라고 볼 수 있다. 하지만 입력 규모가 커지면 속도가 느려질 수 있기 때문에, 문제 상황을 판단하고 적용하는 것이 중요하다.