CS학습2026년 8월 23일

완전 탐색: 가능한 모든 경우를 확인하는 브루트포스(Brute Force) 전략

완전 탐색(Exhaustive Search)은 문제에서 발생 가능한 모든 후보 해를 빠짐없이 검토해서 정답을 찾는 알고리즘 설계 기법이다. 구현이 단순하고 정확성을 보장하지만 입력 크기가 커지면 시간복잡도가 기하급수적 또는 조합적으로 증가한다. 실무에서는 최적화 이전 단계의 기준선(baseline) 구현이나 입력 크기가 작다는 제약이 확실한 경우에 사용한다

송민성5분 읽기

1. 개념

완전 탐색(Exhaustive Search)은 문제의 해가 될 수 있는 모든 경우의 수를 하나도 빠뜨리지 않고 확인해서 조건을 만족하는 답을 찾는 알고리즘 기법이다. 영어로는 브루트포스(Brute Force)라고도 부르며, 문제를 풀기 위한 별도의 통찰이나 수학적 성질을 이용하지 않고 가능한 모든 후보를 순서대로 대입해보는 방식이다.

완전 탐색은 특정 자료구조나 알고리즘 하나를 지칭하는 게 아니라 반복문, 재귀, 백트래킹(Backtracking), 비트마스크(Bitmask) 같은 여러 구현 도구를 활용하는 "접근 전략"이다.

2. 왜 사용하는가

정확성 보장: 모든 경우를 확인하기 때문에 문제 조건만 정확히 구현하면 반드시 정답을 찾는다.
구현 단순성: 최적화된 알고리즘(동적 계획법, 그리디 등)보다 코드가 직관적이고 짧다.
기준선(baseline) 확보: 최적화 알고리즘을 설계하기 전에 완전 탐색으로 정답 여부를 먼저 검증한다.
작은 입력에서의 실용성: 입력 크기가 충분히 작다면(예: N ≤ 20) 완전 탐색만으로도 시간 제한 안에 해결 가능하다.

3. 동작 원리

완전 탐색은 크게 세 가지 구현 방식으로 나뉜다.

단순 반복(Iterative Brute Force): 중첩 반복문으로 모든 조합을 순회한다.
재귀적 완전 탐색(Recursive Exhaustive Search): 선택 트리를 재귀로 순회하며 매 단계마다 가능한 모든 선택지를 시도한다.
백트래킹(Backtracking): 재귀 탐색 중 현재 상태가 조건을 만족할 수 없다고 판단되면 더 깊이 들어가지 않고 즉시 되돌아간다(가지치기, Pruning). 완전 탐색의 성능을 개선한 변형이다.

핵심은 "상태 공간(State Space)"을 정의하고, 그 공간 전체를 체계적으로 순회하는 것이다. 재귀 기반 구현에서는 다음 세 요소가 필요하다.

선택지를 만드는 부분 (다음에 무엇을 시도할지)
종료 조건 (모든 선택이 끝났을 때 정답 여부 판단)
가지치기 조건 (선택적, 백트래킹에서 사용)

4. 코드 예제

예제 1: 단순 반복 — 두 수의 합 문제

배열에서 합이 target이 되는 두 원소의 인덱스를 모두 찾는 완전 탐색이다.

python

def two_sum_brute_force(nums: list[int], target: int) -> list[tuple[int, int]]:
    result = []
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                result.append((i, j))
    return result


if __name__ == "__main__":
    nums = [2, 7, 11, 15, 4]
    target = 9
    print(two_sum_brute_force(nums, target))  # [(0, 1)]

예제 2: 재귀 + 백트래킹 — 부분집합의 합

주어진 배열에서 합이 target이 되는 모든 부분집합을 찾는다. 백트래킹으로 불필요한 탐색을 가지치기한다.

python

def subset_sum(nums: list[int], target: int) -> list[list[int]]:
    result = []
    path = []

    def backtrack(start: int, remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])
            return
        if remaining < 0:
            return  # 가지치기: 남은 값이 음수면 더 진행할 필요 없음

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, remaining - nums[i])
            path.pop()  # 상태 복원

    backtrack(0, target)
    return result


if __name__ == "__main__":
    nums = [3, 1, 4, 2]
    target = 5
    print(subset_sum(nums, target))
    # [[3, 2], [1, 4]]

예제 3: 순열 완전 탐색 — 외판원 문제(TSP)의 브루트포스 해법

도시 4개에 대한 최단 경로를 모든 순열을 확인해서 찾는다. N이 커지면 사용 불가능한 전형적인 완전 탐색 한계 예시다.

python

from itertools import permutations

def tsp_brute_force(dist: list[list[int]]) -> tuple[int, tuple[int, ...]]:
    n = len(dist)
    cities = list(range(1, n))  # 0번 도시를 시작점으로 고정
    best_cost = float("inf")
    best_path = None

    for perm in permutations(cities):
        path = (0,) + perm
        cost = sum(dist[path[i]][path[i + 1]] for i in range(len(path) - 1))
        cost += dist[path[-1]][path[0]]  # 원점 복귀
        if cost < best_cost:
            best_cost = cost
            best_path = path

    return best_cost, best_path


if __name__ == "__main__":
    dist = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0],
    ]
    print(tsp_brute_force(dist))  # (80, (0, 1, 3, 2))

5. 시간 복잡도 또는 성능 특성

| 예제 | 시간복잡도 | 비고 | |---|---|---| | 두 수의 합 (이중 반복문) | O(n²) | n이 10⁴ 이상이면 비효율적, 해시맵으로 O(n) 개선 가능 | | 부분집합의 합 (백트래킹) | 최악 O(2ⁿ) | 가지치기로 실제 수행 시간은 입력에 따라 크게 줄어듦 | | TSP 순열 완전 탐색 | O(n!) | n=10이면 약 362만 번 연산, n=15면 약 1조 번으로 사실상 불가능 |

완전 탐색의 시간복잡도는 대부분 지수 시간(Exponential Time) 또는 계승 시간(Factorial Time)이다. 입력 크기 N이 조금만 커져도 연산량이 폭발적으로 증가하므로, 문제 제약 조건에서 N의 최대값을 반드시 확인하고 완전 탐색이 시간 제한 내에 끝날 수 있는지 사전에 계산해야 한다.

6. 실무 사용 사례

테스트 데이터 검증: 알고리즘 최적화 전에 완전 탐색으로 정답을 구해 놓고, 최적화된 코드의 출력과 비교하는 정합성 테스트에 사용한다.
설정값 튜닝: 하이퍼파라미터 그리드 탐색(Grid Search)처럼 경우의 수가 제한적인 설정 공간을 전수 조사할 때 사용한다.
제약 조건 만족 문제(CSP): 스도쿠, N-Queen 같은 퍼즐을 백트래킹 기반 완전 탐색으로 해결한다.
작은 입력의 조합 최적화: 배송 경로가 5~8개 지점 이내인 소규모 물류 최적화에서는 완전 탐색으로도 실용적인 시간 내 최적해를 구할 수 있다.

7. 주의할 점

입력 크기 확인이 우선: N의 최대값을 보지 않고 완전 탐색을 설계하면 시간 초과(Time Limit Exceeded)로 이어진다. 일반적으로 O(2ⁿ)은 N ≤ 20~25, O(n!)은 N ≤ 10~11 수준에서만 실용적이다.
가지치기 없는 백트래킹은 완전 탐색과 동일: 백트래킹을 쓴다고 항상 빨라지는 게 아니다. 가지치기 조건이 실제로 탐색 공간을 줄이는지 검증해야 한다.
중복 계산 주의: 완전 탐색 도중 동일한 부분 문제를 반복 계산하고 있다면 메모이제이션(Memoization)이나 동적 계획법(Dynamic Programming)으로 전환할 신호다.
재귀 깊이 제한: Python 등 언어의 기본 재귀 깊이 제한(기본 1000)을 초과할 수 있으므로 큰 입력에서는 반복문 기반 구현이나 재귀 깊이 조정을 고려한다.

8. 핵심 정리

완전 탐색은 가능한 모든 후보를 확인해서 정답을 보장하는 가장 기본적인 문제 해결 전략이며, 반복문·재귀·백트래킹으로 구현한다. 구현이 단순하고 정확성이 높지만 시간복잡도가 지수적 또는 계승적으로 증가하므로 입력 크기 제약을 반드시 먼저 확인해야 한다. 실무와 코딩 테스트 모두에서 완전 탐색은 정답 검증용 기준선이자, 문제 구조를 파악한 뒤 동적 계획법이나 그리디 알고리즘 같은 최적화 기법으로 발전시키기 위한 출발점 역할을 한다.