완전탐색 알고리즘(Brute-Force) 총정리: 종류와 자바(Java) 구현

완전탐색 (Brute-Force)이란?

완전탐색 알고리즘(Brute-Force Algorithm)은 문제 해결을 위해 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾아내는 기법입니다. ‘Brute(무식한)’와 ‘Force(힘)’의 합성어로, 말 그대로 무식하게 모든 가능성을 다 찔러본다는 의미를 가지고 있습니다.

완전탐색의 장단점

장점: 알고리즘을 구현하기 쉽고, 해가 존재한다면 반드시 해를 찾을 수 있습니다(100% 정확도 보장).
단점: 모든 경우의 수를 확인해야 하므로 데이터의 개수가 많아지면 실행 시간이 기하급수적으로 증가하여 효율성이 떨어집니다.

완전탐색의 5가지 구현 기법

완전탐색은 문제의 특성에 따라 다양한 방법으로 구현할 수 있습니다. 코딩 테스트에서 자주 등장하는 5가지 유형을 반드시 숙지해야 합니다.

반복문 (For / While)
순열 (Permutation) & 조합 (Combination)
재귀 호출 (Recursive Call / Backtracking)
너비 우선 탐색 (BFS) / 깊이 우선 탐색 (DFS)
비트마스크 (Bitmask)

1. 반복문 (For문) 활용

합이 10인 순서쌍을 구하는 문제

public class For {

    public static int solution() {
        int count = 0;

        for (int i = 0; i <= 10; i++) {
            for (int j = 0; j <= 10; j++) {
                if (i + j == 10) {
                    count++;
                }
            }
        }
        return count;
    }


    public static void main(String[] args) {
        System.err.println(solution()); // 11
    }
}

2. 순열(Permutation)과 조합(Combination)

순서가 중요한지, 중복을 허용하는지에 따라 순열과 조합으로 나뉩니다.

조합 (Combination)

n개 중에서 r개를 순서 없이 뽑는 경우입니다. (예: [1, 2]와 [2, 1]은 같음)

예제: 3개 중 2개를 중복되지 않게 뽑기 (₃C₂)

public class Combination {

    public static void main(String[] args) {
        int n = 3;
        int r = 2;
        int[] resultArr = new int[r];
        combination(resultArr, 0, n, r, 0);

    }

    public static void combination(int[] arr, int index, int n, int r, int target) {
        if (r == 0) {
            print(arr, index);
        } else if (target == n) {
            return;
        } else {
            arr[index] = target;
            combination(arr, index + 1, n, r - 1, target + 1); // target을 뽑는 경우
            combination(arr, index, n, r, target + 1);     // target을 뽑지 않는 경우
        }

    }

    public static void print(int[] arr, int length) {
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }

}
/* Output:
0 1
0 2
1 2
*/

순열 (Permutation)

n개 중에서 r개를 순서 있게 뽑는 경우입니다. (예: [1, 2]와 [2, 1]은 다름)

예제: 3개 중 2개를 순서에 맞게 뽑기 (₃P₂)

public class Permutation {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        permutation(arr, 0, arr.length, 2);
    }

    public static void permutation(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            print(arr, r);
            return;
        }
        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            permutation(arr, depth + 1, n, r);
            swap(arr, i, depth); // 백트래킹 (원상복구)
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void print(int[] arr, int r) {
        for (int i = 0; i < r; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
/* Output:
1 2
1 3
2 1
2 3
3 2
3 1
*/

마치며

완전탐색은 문제의 입력 크기(N)가 작을 때 가장 먼저 고려해야 할 확실한 방법입니다.

참고 사이트

Back to Posts