완전 탐색과 브루트포스 — 모든 풀이의 출발점

최적화된 알고리즘은 어디서 시작될까요? 대부분의 경우, "일단 모든 경우를 다 해보자"에서 출발합니다.

개념 정의

완전 탐색(Exhaustive Search, Brute Force)은 가능한 모든 경우를 하나씩 검사 하여 정답을 찾는 방법입니다. 가장 단순하지만, 정답을 반드시 보장한다는 강력한 장점이 있습니다.

왜 완전 탐색부터 시작하는가

**정확성 보장 **: 모든 경우를 확인하므로 답을 놓칠 수 없습니다.
** 기준선 역할 **: 최적화된 풀이의 정답 여부를 검증하는 기준이 됩니다.
** 문제 이해 **: 완전 탐색을 구현하면서 문제의 구조와 패턴을 파악할 수 있습니다.
** 실전에서 통과 **: n이 작으면 완전 탐색만으로도 시간 안에 해결됩니다.

시간 복잡도 예측

완전 탐색의 가능 여부를 판단하려면, 경우의 수와 연산 횟수를 추정해야 합니다.

기준: 1초에 약 1억 번 연산

시간 복잡도	n의 대략적 한계
O(n!)	n ≤ 10~11
O(2^n)	n ≤ 20~25
O(n³)	n ≤ 500
O(n²)	n ≤ 10,000
O(n log n)	n ≤ 1,000,000
O(n)	n ≤ 10,000,000

이 표를 머릿속에 갖고 있으면, 문제를 보자마자 "완전 탐색이 되는가?"를 빠르게 판단할 수 있습니다.

순열 열거

n개의 원소를 모든 순서로 나열하는 것입니다. 경우의 수: n!

JAVA

public static void permutation(int[] arr, int depth, int n) {
    if (depth == n) {
        System.out.println(Arrays.toString(arr));
        return;
    }

    for (int i = depth; i < n; i++) {
        swap(arr, depth, i);      // 선택
        permutation(arr, depth + 1, n); // 재귀
        swap(arr, depth, i);      // 원상복구
    }
}

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

Java의 다음 순열 (Next Permutation)

사전순으로 다음 순열을 구하는 방법입니다. 재귀 없이 모든 순열을 생성할 수 있습니다.

JAVA

public static boolean nextPermutation(int[] arr) {
    int n = arr.length;
    int i = n - 2;

    // 1. 뒤에서부터 감소하기 시작하는 지점 찾기
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i < 0) return false; // 마지막 순열

    // 2. arr[i]보다 큰 가장 작은 원소와 교환
    int j = n - 1;
    while (arr[j] <= arr[i]) j--;
    swap(arr, i, j);

    // 3. i+1 이후를 뒤집기 (오름차순으로)
    reverse(arr, i + 1, n - 1);
    return true;
}

조합 열거

n개에서 r개를 선택하는 모든 경우. 경우의 수: nCr

JAVA

public static void combination(int[] arr, int n, int r,
                                int start, int depth, int[] selected) {
    if (depth == r) {
        System.out.println(Arrays.toString(selected));
        return;
    }

    for (int i = start; i < n; i++) {
        selected[depth] = arr[i];
        combination(arr, n, r, i + 1, depth + 1, selected);
    }
}

부분 집합 열거

각 원소를 포함/불포함하는 모든 경우. 경우의 수: 2^n

재귀 방식

JAVA

public static void subsets(int[] arr, int index, List<Integer> current) {
    if (index == arr.length) {
        System.out.println(current);
        return;
    }

    // 포함하지 않는 경우
    subsets(arr, index + 1, current);

    // 포함하는 경우
    current.add(arr[index]);
    subsets(arr, index + 1, current);
    current.remove(current.size() - 1);
}

비트마스크 방식

JAVA

public static void subsetsWithBitmask(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);
    }
}

비트마스크 방식은 코드가 간결하고, 집합의 상태를 정수 하나로 표현할 수 있어서 DP와 결합하기 좋습니다.

중복 순열과 중복 조합

중복 순열: n개에서 r개를 중복 허용하여 나열

JAVA

public static void permutationWithRepetition(int[] arr, int r,
                                              int depth, int[] selected) {
    if (depth == r) {
        System.out.println(Arrays.toString(selected));
        return;
    }

    for (int i = 0; i < arr.length; i++) {
        selected[depth] = arr[i]; // 이미 선택한 것도 다시 선택 가능
        permutationWithRepetition(arr, r, depth + 1, selected);
    }
}

중복 조합: n개에서 r개를 중복 허용하여 선택

JAVA

public static void combinationWithRepetition(int[] arr, int r,
                                              int start, int depth, int[] selected) {
    if (depth == r) {
        System.out.println(Arrays.toString(selected));
        return;
    }

    for (int i = start; i < arr.length; i++) {
        selected[depth] = arr[i];
        combinationWithRepetition(arr, r, i, depth + 1, selected); // i+1이 아닌 i
    }
}

완전 탐색 전략 선택

문제를 보고 어떤 열거 방법을 쓸지 결정하는 것이 중요합니다.

문제 유형	열거 방법	경우의 수
순서가 중요	순열	n!
순서 무관, 선택만	조합	nCr
포함/불포함	부분 집합	2^n
중복 허용 순서	중복 순열	n^r
중복 허용 선택	중복 조합	n+r-1Cr

최적화 전 완전 탐색의 중요성

Step 1: 완전 탐색으로 정답 구현

JAVA

// 배열에서 합이 target인 부분 집합 찾기 — O(2^n)
public static boolean subsetSum(int[] arr, int target) {
    int n = arr.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sum += arr[i];
            }
        }
        if (sum == target) return true;
    }
    return false;
}

Step 2: 패턴 발견 → 최적화

위 문제가 n ≤ 100이라면? 2^100은 불가능합니다. DP로 전환합니다.

JAVA

// DP: O(n × target)
public static boolean subsetSumDP(int[] arr, int target) {
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : arr) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

완전 탐색 → DP, 그리디, 이진 탐색 등으로의 최적화 경로를 파악하는 것이 알고리즘 실력의 핵심입니다.

백엔드/실무에서의 연결

테스트 케이스 생성

모든 입력 조합을 테스트하는 것은 완전 탐색입니다. 작은 입력에 대해 모든 경우를 시도하여 엣지 케이스를 발견합니다.

설정 조합 탐색

시스템 성능 튜닝에서 여러 파라미터 조합을 시도하는 것도 완전 탐색입니다. Grid Search(하이퍼파라미터 튜닝)가 대표적입니다.

권한 조합

역할(Role) 기반 권한 시스템에서 "이 사용자가 이 작업을 할 수 있는가?"를 판단할 때, 가진 권한의 조합을 확인합니다.

데이터 검증

데이터 무결성 검증에서 모든 레코드를 순회하며 조건을 확인하는 것은 O(n) 완전 탐색입니다. 인덱스가 없는 상태에서의 검색도 마찬가지입니다.

주의할 점

시간 복잡도 계산 없이 완전 탐색을 제출하는 실수

완전 탐색의 시간 복잡도가 문제의 입력 범위에서 허용 가능한지 반드시 확인해야 합니다. n이 20이면 O(2^n) = 약 100만으로 가능하지만, n이 30이면 O(2^n) = 약 10억으로 시간 초과입니다.

중복 탐색을 인지하지 못하는 실수

순열이 필요한데 조합을 생성하거나, 조합이 필요한데 순열을 생성하면 탐색량이 수배~수십배 차이납니다. "순서가 중요한가?"를 먼저 판단해야 합니다.

정리

기억할 포인트:

완전 탐색은 ** 정답을 보장하는 가장 확실한 방법 **입니다.
문제를 보면 먼저 경우의 수를 추정하세요. n ≤ 20이면 2^n, n ≤ 10이면 n!이 가능합니다.
순열/조합/부분집합 중 어떤 열거가 필요한지 판단하는 것이 첫걸음입니다.
완전 탐색이 시간 초과라면, 패턴을 발견하여 DP/그리디/이진 탐색으로 최적화하세요.
"일단 되게 만들고, 그다음에 빠르게 만든다" 가 알고리즘의 기본 원칙입니다.