브루트포스(Brute Force)

정의

Brute Force(브루트포스)란?

브루트포스(Brute Force)는 가능한 모든 경우의 수를 직접 시도하여 정답을 찾는 방식입니다. “정답이 될 수 있는 후보를 전부 검사한다”가 핵심이며, 보통 구현이 단순하고 실수가 적어 코딩테스트의 출발점으로 자주 사용됩니다.

브루트포스 = 후보 생성(Generate) + 후보 검증(Check)

예) “분해합”은 후보 x를 생성하고, d(x)=N인지 검증하는 전형적인 브루트포스 문제입니다.

핵심 메시지

브루트포스는 “무식하게 다 해보는 것”이 아니라, 후보 공간을 얼마나 깔끔하게 정의하고 줄이느냐에 따라 가장 강력하고 안정적인 풀이가 될 수 있습니다.

 

수학·컴퓨터 과학 관점

브루트포스는 “탐색”의 가장 기본 형태

브루트포스는 탐색(Search) 문제를 가장 직접적으로 푸는 방식입니다. 수학적으로는 “가능한 해의 집합”을 정의하고, 컴퓨터로는 “그 집합을 순회하며 조건을 만족하는지 검사”합니다.

(1) 후보 공간(Search Space) 정의

어떤 값들이 정답 후보인지 먼저 정합니다. (예: x는 1부터 N까지)

(2) 검증 함수(Check Function) 정의

후보가 정답인지 확인하는 조건을 구현합니다. (예: d(x) == N)

(3) 시간복잡도/상한 판단

후보 개수 × 검증 비용이 제한 시간 안에 들어오는지 판단합니다.

구성 요소	설명	예시
Generate	후보를 만들어낸다	x=1..N 순회
Check	정답 조건을 만족하는지 검사	d(x)==N
Prune	불필요한 후보를 줄인다	start=N-9×digits

 

알고리즘 설계

“브루트포스가 통과하는” 조건을 만드는 법

브루트포스가 실패하는 대부분의 이유는 “너무 많은 후보” 때문입니다. 그래서 브루트포스는 보통 아래 3가지 레버로 통과하게 만듭니다.

1

탐색 범위 줄이기 (상한/하한)

수학적 상한을 잡아 “어차피 불가능한 후보”를 제거합니다.

2

검증 비용 줄이기

후보 하나를 검사하는 데 드는 연산을 최소화합니다.

3

조기 종료(Early Exit)

정답을 찾는 즉시 종료해 평균 수행 시간을 크게 줄입니다.

특히 “분해합”은 start=N-9×digits로 범위를 줄이고, 첫 해답에서 종료하는 대표적인 “잘 설계된 브루트포스” 예시입니다.

 

구현

Java 예시: “분해합(생성자)”는 브루트포스의 정석

import java.io.*;

public class BruteForceExample {

    static int digitSum(int x) {
        int s = 0;
        while (x > 0) {
            s += (x % 10);
            x /= 10;
        }
        return s;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());

        int digits = String.valueOf(N).length();
        int start = Math.max(1, N - 9 * digits); // 브루트포스 범위 줄이기(Prune)

        int answer = 0;
        for (int x = start; x <= N; x++) {       // 후보 생성(Generate)
            int value = x + digitSum(x);         // 후보 검증(Check)
            if (value == N) {                    // 조기 종료(Early Exit)
                answer = x;
                break;
            }
        }
        System.out.println(answer);
    }
}

 

요약

체크리스트로 마무리

CHECK

✅ 브루트포스 = 후보 생성(Generate) + 검증(Check)

✅ 통과 전략 = 범위 줄이기(Prune) + 검증 최적화 + 조기 종료

✅ 먼저 브루트포스로 풀고, 안 되면 최적화/다른 알고리즘으로 이동