브루트포스 알고리즘이란?

브루트포스(Brute Force) 알고리즘은 알고리즘 문제를 처음 접하는 순간 가장 먼저 마주하게 되는 방식이며, 이름처럼 모든 경우의 수를 전체 다 시도해 답을 찾는 방식이다.

복잡한 최적화 기법이 없기에 구현도 단순하지만 입력값이 늘어날수록 시간복잡도가 기하급수적으로 증가하기 때문에 입력 데이터의 양을 보고 접근을 해야 한다.

브루트포스 알고리즘의 특징

• 가능한 모든 경우를 하나도 빠짐없이 탐색하여 조건을 만족하는 해를 찾는 알고리즘이기에 정답이존재하면 무조건 정답을 찾을 수 있음
• 논리적으로 가장 직관적인 접근
• 최적해를 보장
• 경우의 수가 많아지면 시간 초과 위험성 급증

브루트포스의 시간복잡도

문제 유형	시간복잡도 예시
단순 반복	O(N)
이중 반복	O(N²)
모든 순열	O(N!)
모든 부분집합	O(2ⁿ)

이처럼 시간 복잡도가 기하급수적으로 늘어나기에 입력 범위를 잘 확인해야한다.
하지만 N의 값이 작다면 브루트포스 알고리즘은 매우 좋은 선택지가 된다.

대표적인 문제 유형

지금까지 문제들을 풀어봤을 때

• 모든 경우를 확인
• N < 100
• 가능한 경우 중 최대/최소를 구하라

같은 조건이 나올 때 브루트포스 알고리즘이 쓰이는 경우가 많았다.

대표적인 브루트포스 + 백트래킹 문제인 N-QUEEN 문제에서도 N의 범위가 15 미만으로 매우 작고, 가능한 경우의 최대 경우의 수를 구하게 나오고 있다.

브루트포스 알고리즘의 적용 예시

https://www.acmicpc.net/problem/1065

public class boj_1065_S4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // N <= 1000
        int N = Integer.parseInt(st.nextToken());

        if (N == 1000) N = 999;

        if (N < 100) {
            System.out.println(N);
        }
        else {
            int count = 99;

            // O(3N) -> O(N)
            for (int i = 100; i < N + 1; i++) {
                int[] arr = new int[3];
                int temp = i;

                for (int j = 0; j < 3; j++) {
                    arr[j] = temp % 10;
                    temp /= 10;
                }

                int check = arr[1] - arr[0];

                if (check == arr[2] - arr[1]) count++;
            }

            System.out.println(count);
        }

        br.close();
    }
}

이 문제는 1부터 N까지의 모든 정수 후보들 중에서 정수 i가 한수인지 아닌지를 전수 검사하는 문제이다.

중간에 탐색 조건을 줄이기는 했지만 그 이외의 모든 대상을 전수 검사하기에 브루트포스 알고리즘이 적용이 되는 것이다.

이전의 브루트포스 알고리즘의 시간복잡도 설명에서 말한 것처럼 여기에서는 단순 반복으로 O(N) 시간복잡도가 적용이 된다.