완전탐색 알고리즘(Brute-Force) 완벽 가이드: 개념, 시간복잡도, 자바(Java) 구현

완전탐색 알고리즘(Brute-Force)이란?

완전탐색 알고리즘(Brute-Force Algorithm)은 컴퓨터 과학에서 해를 구하기 위해 가능한 모든 경우의 수를 전부 탐색하는 방식을 말합니다. 영어로는 ‘Brute(무식한)’와 ‘Force(힘)’의 합성어로, “무식하게 힘으로 밀어붙인다”는 뜻을 가지고 있습니다. 다른 말로 전수 조사(Exhaustive Search)라고도 부릅니다.

왜 완전탐색을 배워야 할까?

코딩 테스트나 알고리즘 문제 해결의 기본은 “문제를 어떻게 풀 것인가?”를 설계하는 것입니다. 가능한 경우의 수가 적다면(N이 작다면), 복잡한 알고리즘(DP, 그리디 등)을 고민할 필요 없이 완전탐색으로 푸는 것이 가장 빠르고 정확합니다.

완전탐색의 장단점

장점 (Pros):
- 정확성 100%: 모든 가능성을 검토하므로 해가 존재한다면 반드시 찾을 수 있습니다.
- 구현 편의성: 알고리즘 로직이 단순하여 구현하기 쉽습니다.
단점 (Cons):
- 효율성 저하: 데이터(N)가 많아지면 연산량이 기하급수적으로 늘어납니다 (Exponential Time).
- 실행 시간: 시간 복잡도가 높아 제한 시간 내에 해결하지 못할 수 있습니다.

완전탐색의 시간 복잡도와 적용 기준

완전탐색을 적용할 때는 입력 크기(N)를 반드시 확인해야 합니다. 일반적으로 시간 제한이 1초라면 약 1억 번의 연산이 가능하다고 가정합니다.

N이 10 이하: O(N!) (순열) → 3,628,800번 (가능)
N이 20 이하: O(2^N) (재귀/부분집합) → 1,048,576번 (가능)
N이 100 이하: O(N^3) (3중 for문) → 1,000,000번 (가능)
N이 1,000 이하: O(N^2) (2중 for문) → 1,000,000번 (가능)
N이 100,000 이상: O(N log N) 또는 O(N) 필요 → 완전탐색 불가능

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

코딩 테스트에서 자주 등장하는 완전탐색 유형은 크게 5가지가 있습니다.

단순 반복문 (For / While): 특정 범위의 값을 모두 확인
순열 (Permutation): 서로 다른 N개에서 R개를 순서 있게 뽑는 경우
조합 (Combination): 서로 다른 N개에서 R개를 순서 없이 뽑는 경우
재귀 호출 / 백트래킹 (Recursive / Backtracking): 상태 공간 트리를 탐색하며 해를 찾음
비트마스크 (Bitmask): 2진수를 이용해 집합(Subset)을 표현하고 연산

각 기법별로 자바(Java) 구현 예제를 살펴보겠습니다.

1. 단순 반복문 (Simple Iteration)

가장 직관적인 방법으로, for나 while문을 중첩하여 모든 경우의 수를 확인합니다. 비밀번호(0000~9999)를 찾는 것처럼 범위가 명확할 때 사용합니다.

// 예제: 합이 10이 되는 두 수(0~10) 찾기
public class BruteForceLoop {
    public static void main(String[] args) {
        int count = 0;
        // 2중 반복문으로 모든 (i, j) 조합 확인: O(N^2)
        for (int i = 0; i <= 10; i++) {
            for (int j = 0; j <= 10; j++) {
                if (i + j == 10) {
                    System.out.println("Pair found: " + i + ", " + j);
                    count++;
                }
            }
        }
        System.out.println("Total count: " + count);
    }
}

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

순서가 중요한지, 중복을 허용하는지에 따라 순열과 조합으로 나뉩니다. N개의 원소 중 R개를 뽑는 경우의 수를 모두 구해야 할 때 사용합니다.

2-1. 조합 (Combination: nCr)

순서 상관없이 n개 중에서 r개를 선택하는 경우입니다. (예: {1, 2} == {2, 1}) 재귀 함수를 이용하여 현재 원소를 ‘선택함’과 ‘선택하지 않음’ 두 가지 분기로 나누어 탐색합니다.

// 조합 구현: 3개 중 2개를 뽑는 경우 (3C2)
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) { // r개를 모두 뽑았을 때 출력
            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();
    }
}

2-2. 순열 (Permutation: nPr)

순서를 고려하여 n개 중에서 r개를 나열하는 경우입니다. (예: {1, 2} != {2, 1}) swap을 이용하거나 visited 배열을 사용하여 구현할 수 있습니다.

// 순열 구현: 3개 중 2개를 순서 있게 뽑는 경우 (3P2)
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) { // r개를 모두 선택했을 때
            print(arr, r);
            return;
        }
        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);        // 현재 depth의 원소와 i번째 원소를 교환
            permutation(arr, depth + 1, n, r); // 다음 depth로 이동
            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();
    }
}

3. 재귀 호출 (Recursive Call) & 백트래킹 (Backtracking)

백트래킹(Backtracking)은 해를 찾아가는 과정에서 “가망이 없는 경로”를 미리 차단(Pruning, 가지치기)하여 탐색 범위를 줄이는 기법입니다. 주로 재귀 함수로 구현하며, N-Queen 문제가 대표적입니다. 완전탐색의 일종이지만, 불필요한 연산을 줄여 효율성을 높입니다.

// 백트래킹 예제: 부분집합(Subset) 구하기
public class Subset {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        boolean[] visited = new boolean[arr.length];
        powerSet(arr, visited, 3, 0); // 3개의 원소에 대한 부분집합
    }

    public static void powerSet(int[] arr, boolean[] visited, int n, int idx) {
        if (idx == n) {
            print(arr, visited, n);
            return;
        }

        visited[idx] = false; // 현재 원소 선택 X
        powerSet(arr, visited, n, idx + 1);

        visited[idx] = true;  // 현재 원소 선택 O
        powerSet(arr, visited, n, idx + 1);
    }
}

4. 비트마스크 (Bitmask)

2진수 비트 연산을 이용해 집합의 포함 여부를 검사하는 방법입니다. visited 배열 대신 정수 하나로 상태를 표현할 수 있어 메모리를 절약하고 연산 속도가 빠릅니다.

Target & (1 << i): i번째 원소가 포함되어 있는지 확인
Target | (1 << i): i번째 원소를 추가

5. BFS / DFS (너비 우선 탐색 / 깊이 우선 탐색)

그래프 탐색 알고리즘이지만, 모든 경우를 탐색한다는 점에서 완전탐색의 범주에 포함됩니다.

BFS (Queue 사용): 최단 경로 문제 해결에 적합
DFS (Stack/Recursion 사용): 미로 찾기, 경로의 특징을 저장해야 하는 경우 적합

참고 사이트

Back to Posts