브루트 포스 (Brute Force) 알고리즘이란?

개념

알고리즘 문제를 풀다 보면 "브루트 포스(Brute Force)" 라는 개념을 자주 접하게 된다. 브루트 포스란 가장 직관적이고 단순한 방식으로 문제를 해결하는 기법으로, 가능한 모든 경우의 수를 탐색하여 정답을 찾는 방식이다.

이 개념을 쉽게 이해할 수 있는 예시가 바로 자물쇠 비밀번호 찾기이다. 어렸을 적 사물함 비밀번호를 잃어버린 경험이 있다면, 000부터 999까지 차례로 숫자를 하나씩 입력해보며 정답을 찾으려 했던 적이 있을 것이다. 이처럼 가능한 모든 경우를 하나씩 시도하는 방식이 바로 브루트 포스다.

이 방법은 "무식하게 힘으로 푼다" 라는 의미 그대로, 정답을 보장할 수 있지만 비효율적일 수도 있다. 그럼에도 불구하고, 구현이 쉽고 직관적이기 때문에 많은 문제에서 기초적인 접근법으로 사용된다.

 

브루트 포스의 활용 예시

예제 1) 비밀번호 찾기 (단순한 경우의 수 탐색)

비밀번호가 4자리 숫자로 이루어져 있고, 0000부터 9999까지 가능하다고 가정하여 브루트 포스를 사용하면 다음과 같이 해결할 수 있음

public class BruteForcePassword {
    public static void main(String[] args) {
        int correctPassword = 8743; // 정답 비밀번호
        
        for (int password = 0; password <= 9999; password++) {
            if (password == correctPassword) {
                System.out.println("비밀번호 찾음: " + password);
                break;
            }
        }
    }
}

이 방법은 단순하지만, 최대 10,000번의 연산이 필요하며 비효율적이다. 시간 복잡도는 O(N)이다.

예제 2) 배열에서 두 수의 합 찾기 (완전 탐색)

배열 arr에서 두 수를 더해서 target이 되는 모든 조합을 찾는 문제

public class BruteForceTwoSum {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 6;

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] + arr[j] == target) {
                    System.out.println("두 수: " + arr[i] + ", " + arr[j]);
                }
            }
        }
    }
}

위 코드는 O(N²)의 시간 복잡도를 가지며, 입력 크기가 커질수록 실행 시간이 급격히 증가한다.

브루트 포스의 시간 복잡도

브루트 포스 알고리즘은 가능한 모든 경우를 시도하기 때문에 일반적으로 높은 시간 복잡도를 가진다.

문제 유형 브루트 포스 접근법 시간 복잡도

비밀번호 찾기 (0000~9999)	단순 반복문	O(N)
두 수의 합 찾기	이중 반복문	O(N²)
순열 생성	모든 조합 탐색	O(N!)
문자열 패턴 매칭	문자열 전체 비교	O(N*M) (N: 텍스트 길이, M: 패턴 길이)

위 표에서 볼 수 있듯이, 입력 크기가 커질수록 연산 횟수가 기하급수적으로 증가하기 때문에 최적화 기법이 필요하다.

브루트 포스를 개선하는 방법

브루트 포스의 단점을 해결하기 위해 다음과 같은 방법을 사용할 수 있다.

1. 백트래킹 (Backtracking)
   • 불필요한 탐색을 줄여 효율성을 높이는 기법
   • 예)  N-Queen 문제, 순열/조합 문제
2. 가지치기 (Pruning)
   • 특정 조건을 만족하지 않으면 탐색을 중단하는 방식
   • 예) 최소 비용을 찾는 문제에서, 현재 비용이 최적해보다 크다면 탐색 종료
3. 그리디 알고리즘(Greedy Algorithm)
   • 매 순간 최선의 선택을 하여 탐색 범위를 줄임
   • 예) 동전 거스름돈 문제
4. 다이나믹 프로그래밍 (Dynamic Programming)
   • 중복 계산을 피하며 최적화
   • 예) 피보나치 수열, 배낭 문제

결론

브루트 포스는 가장 기본적이고 직관적인 알고리즘으로, 문제를 처음 접근할 때 가장 먼저 떠올릴 수 있는 방법이지만 입력 크기가 커질수록 실행 시간이 길어지므로, 효율적인 알고리즘으로 개선할 필요가 있다.

문제를 해결할 때는

1. 브루트 포스로 먼저 접근해 보고,
2. 시간 복잡도를 분석한 후
3. 더 나은 알고리즘을 찾아 최적화

라는 기준으로 알고리즘 문제를 풀어보는것이 가장 효율적인 방법인거 같다.