완전 탐색 (Brute Force)

Jeonghwan Yoon·2025년 3월 30일

완전 탐색이란?

가능한 모든 경우의 수를 전부 탐색해 정답을 찾는 방법
입력 크기(N)가 작을 때 사용할 수 있는 기본적인 알고리즘 전략
무조건 정답을 찾을 수 있지만, 효율성은 낮을 수 있음

사용 시점

조합, 순열, 부분집합 등 경우의 수가 크지 않을 때
빠른 알고리즘이 떠오르지 않을 때, 기본적으로 시도해 볼 수 있음
완전 탐색으로 먼저 짠 뒤, 최적화 알고리즘으로 개선

완전 탐색의 대표 유형

유형	설명	시간 복잡도
순열 (Permutation)	순서를 고려해 R개 선택	O(N!)
조합 (Combination)	순서 없이 R개 선택	O(2ⁿ) 이하
부분집합 (Subset)	각 원소를 포함/제외	O(2ⁿ)
중첩 반복문	for문으로 모든 조합 탐색	O(N²) ~ O(N³)

순열 예시

def permute(arr):
    result = []
    used = [False] * len(arr)
    def backtrack(path):
        if len(path) == len(arr):
            result.append(path[:])
            return
        for i in range(len(arr)):
            if not used[i]:
                used[i] = True
                path.append(arr[i])
                backtrack(path)
                path.pop()
                used[i] = False
    backtrack([])
    return result

조합 예시

def combine(arr, r):
    result = []
    def backtrack(start, path):
        if len(path) == r:
            result.append(path[:])
            return
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

부분집합 예시

def subsets(arr):
    result = []
    def backtrack(index, path):
        if index == len(arr):
            result.append(path[:])
            return
        path.append(arr[index])
        backtrack(index + 1, path)
        path.pop()
        backtrack(index + 1, path)
    backtrack(0, [])
    return result

중첩 반복문 예시 (3중 for문)

arr = [-1, 0, 1, 2, -1, -4]
n = len(arr)
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if arr[i] + arr[j] + arr[k] == 0:
                print(arr[i], arr[j], arr[k])

시간 복잡도 판단 기준

N 크기	사용 가능한 탐색 범위
N ≤ 10	O(N!), O(2ⁿ) 가능
N ≤ 15	O(2ⁿ) 가능
N ≤ 100	O(N²) 가능
N ≤ 1000	O(N log N) 필요
N ≥ 100,000	O(N), O(1)만 가능

정리

비교 항목	완전 탐색	최적화 알고리즘
정확도	정답 보장	정답 아닐 수도 있음
속도	느림	빠름
난이도	구현 쉬움	복잡한 로직 가능
사용 조건	경우의 수 작을 때	데이터 크기 클 때