[Algorithms] 브루트 포스 알고리즘

Brute Force 알고리즘?

브루트포스는 한국어로 무식한 힘이라는 뜻을 가졌으며 완전 탐색 알고리즘의 한 종류입니다.

전공자 용어로는 하드코딩이며, 브루트포스 알고리즘은 완전탐색으로 답을 도출하는 알고리즘입니다.

 

모든 경우의 수를 전부 탐색하기 때문에, 100% 정확성을 보장하지만 그만큼의 높은 시간 복잡도를 갖습니다.

 

비전공자분들의 이해를 돕기위해 예시)

자물쇠 비밀번호를 잊어버렸을 때 000 ~ 999까지 모든 조합을 시도해보는 방법입니다.

 

 

완전탐색과 브루트포스의 차이점

완전탐색과 브루트포스는 같은 개념이다.

 

완전탐색 : 문제 해결 방법론적 관점에서의 용어

모든 경우의 수를 전부 탐색하는 방식의 알고리즘 - 결과보다는 탐색 과정의 중점

 

브루트포스 : 구현 방식 관점에서의 용어

모든 경우를 탐색하고 답을 도출하는 알고리즘 - 결과를 찾는 것이 중점

 

 

왜 사용하나요?

정확성 보장 : 모든 경우의 수를 검사하므로 반드시 정답을 찾을 수 있음

구현 용이성 : 다른 알고리즘에 비해 구현이 쉬움

디버깅 편의성 : 로직이 단순하여 오류 발견이 쉬움

 

브루트포스 알고리즘 사용 조건

1. 문제의 크기가 비교적으로 작을 때

예시 ) 자물쇠 조합이 000 ~ 999  ( 자물쇠가 아닌 금고를 따려고 하면 안됨 )

 

2. 더 효율적인 알고리즘이 없거나, 찾기 어려울 때 

 

3. 최적해를 반드시 찾아야 하는 경우

 

4. 알고리즘의 정확성을 검증하기 위한 기준 솔루션이 필요할 때

 

 

브루트포스 알고리즘 구현 예제

1. 반복문을 사용한 방식

• 가장 직관적인 구현 방법
• 중첩 반복문을 사용하여 모든 경우를 확인
• 문제의 크기가 작을 때 효과적임

public class BruteForceExamples {
    
    /**
     * 1. 반복문을 사용한 브루트포스 - 순열 찾기
     * 세 자리 숫자에서 모든 가능한 순열을 찾는 예제
     */
    public static void findPermutationsIterative() {
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                if (j != i) {
                    for (int k = 1; k <= 3; k++) {
                        if (k != i && k != j) {
                            System.out.println(i + "" + j + "" + k);
                        }
                    }
                }
            }
        }
    }

 

 

 

 

2. 재귀를 사용한 방식

• 문제를 작은 부분 문제로 나누어 해결
• 복잡한 문제를 간단한 코드로 구현 가능
• 함수 호출 스택 관리에 주의 필요함.

/**
     * 2. 재귀를 사용한 브루트포스 - 부분집합 찾기
     * 주어진 배열의 모든 부분집합을 찾는 예제
     */
    public static void findSubsets(int[] arr, int index, List<Integer> current) {
        if (index == arr.length) {
            System.out.println(current);
            return;
        }
        
        // 현재 원소를 포함하지 않는 경우
        findSubsets(arr, index + 1, current);
        
        // 현재 원소를 포함하는 경우
        current.add(arr[index]);
        findSubsets(arr, index + 1, current);
        current.remove(current.size() - 1);
    }

 

 

3. 동적 프로그래밍(DP)을 활용한 방식

• 중복 계산을 피하기 위해 결과를 저장하고 재사용
• 메모리를 더 사용하는 대신 실행 시간을 단축
• 특정 패턴이 반복되는 문제에 효과적

/**
     * 3. DP를 활용한 브루트포스 - 최적 부분집합 합 찾기
     * 배열에서 특정 합을 만들 수 있는지 확인하는 예제
     */
    public static boolean canMakeSum(int[] nums, int targetSum) {
        boolean[][] dp = new boolean[nums.length + 1][targetSum + 1];
        
        // 초기화: 합이 0인 경우는 항상 가능
        for (int i = 0; i <= nums.length; i++) {
            dp[i][0] = true;
        }
        
        // 모든 가능한 부분집합의 합을 계산
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= targetSum; j++) {
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        return dp[nums.length][targetSum];
    }

 

 

4. 비트마스크를 활용한 방식

• 비트 연산을 통해 효율적으로 부분집합 생성
• 메모리 사용량이 적음
• 구현이 간결하고 실행 속도가 빠름

 /**
     * 4. 비트마스크를 활용한 브루트포스 - 모든 부분집합 생성
     * 비트연산을 통해 효율적으로 모든 부분집합을 생성하는 예제
     */
    public static void generateSubsetsBitMask(int[] arr) {
        int n = arr.length;
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(arr[i]);
                }
            }
            System.out.println(subset);
        }
    }
}

 

 

 

브루트포스를 사용할 때는 특정 솔루션에만 효율적이니, 더 효율적인 방법이 없는지 생각한뒤

사용하여야 한다.