완전탐색 — Brute Force

이 토픽을 마치면

완전탐색이 적합한 상황을 판단할 수 있고, 반복문, 순열, 조합을 활용해서 모든 경우의 수를 체계적으로 탐색할 수 있습니다.

가장 확실한 방법

비밀번호가 4자리 숫자라면, 0000부터 9999까지 전부 시도하면 반드시 찾을 수 있습니다. 이것이 완전탐색(Brute Force, Exhaustive Search)입니다.

python

# 4자리 숫자 비밀번호 전수 조사
for code in range(10000):
    if check(code):
        print(f"비밀번호: {code:04d}")
        break

10,000가지. 컴퓨터에게는 눈 깜짝할 시간입니다.

완전탐색의 핵심: "빠뜨리는 경우가 없으므로 답이 반드시 나온다." 정확성이 보장된다는 것이 최대 장점입니다.

언제 쓰는가

경우의 수가 충분히 적을 때 완전탐색을 씁니다.

text

1초에 약 1억(10^8)번 연산 가능 기준:
  n ≤ 20     → 2^20 = 약 100만 ✅
  n ≤ 10     → 10! = 약 360만 ✅
  n ≤ 8      → 8! = 40,320 ✅
  n ≤ 25~30  → 2^30 = 약 10억 ⚠️ 시간 초과 위험

코딩 테스트에서 입력 크기가 작으면(n ≤ 20 정도) 완전탐색을 먼저 떠올려야 합니다. 복잡한 알고리즘을 쓰기 전에 "그냥 다 해보면 되는 거 아닌가?"를 먼저 확인하는 것입니다.

패턴 1 — 중첩 반복문

가장 기본적인 형태입니다:

python

# 두 수의 합이 target인 쌍 찾기
def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

모든 쌍을 시도합니다. O(n²)이지만, n이 작으면 충분합니다.

패턴 2 — 순열 (Permutation)

순서가 중요한 모든 경우:

python

from itertools import permutations

# [1, 2, 3]의 모든 배열 순서
for p in permutations([1, 2, 3]):
    print(p)
# (1, 2, 3)
# (1, 3, 2)
# (2, 1, 3)
# (2, 3, 1)
# (3, 1, 2)
# (3, 2, 1)

n개의 순열은 n!가지입니다. 3! = 6, 5! = 120, 10! = 3,628,800.

python

# 숫자 카드로 만들 수 있는 가장 큰 수
cards = [3, 1, 4]
max_num = 0
for p in permutations(cards):
    num = int("".join(map(str, p)))
    max_num = max(max_num, num)

print(max_num)  # 431

패턴 3 — 조합 (Combination)

순서가 상관없는 모든 경우:

python

from itertools import combinations

# 5명 중 3명을 고르는 모든 방법
people = ["A", "B", "C", "D", "E"]
for team in combinations(people, 3):
    print(team)
# ('A', 'B', 'C')
# ('A', 'B', 'D')
# ('A', 'B', 'E')
# ... 총 10가지 (5C3 = 10)

python

# 주어진 메뉴에서 2개를 골라 합이 가장 싼 조합
prices = {"라면": 3500, "김밥": 2500, "떡볶이": 4000, "순대": 3000}
items = list(prices.items())

cheapest = float('inf')
best_combo = None
for combo in combinations(items, 2):
    total = combo[0][1] + combo[1][1]
    if total < cheapest:
        cheapest = total
        best_combo = (combo[0][0], combo[1][0])

print(f"{best_combo}: {cheapest}원")  # ('김밥', '순대'): 5500원

패턴 4 — 비트마스크

각 요소를 "선택/비선택"으로 나누는 부분집합 문제:

python

# n개의 부분집합 = 2^n개
items = ["사과", "바나나", "체리"]
n = len(items)

for mask in range(1 << n):  # 0 ~ 2^n - 1
    subset = []
    for i in range(n):
        if mask & (1 << i):
            subset.append(items[i])
    print(subset)

# []
# ['사과']
# ['바나나']
# ['사과', '바나나']
# ['체리']
# ['사과', '체리']
# ['바나나', '체리']
# ['사과', '바나나', '체리']

1 << n은 2^n입니다. 비트 하나가 "이 요소를 포함할지 말지"를 결정합니다.

완전탐색에서 최적화로

완전탐색으로 먼저 정답을 구한 후, 성능이 부족하면 최적화합니다:

완전탐색	→	최적화 기법
모든 쌍 (O(n²))	→	해시 맵 (O(n))
모든 부분합	→	투 포인터, 슬라이딩 윈도우
모든 경로	→	DP (메모이제이션)
전수 조사	→	가지치기 (pruning)

코딩 테스트 풀이 순서:

완전탐색으로 정확한 풀이를 먼저 작성
시간 초과가 나면 규칙성을 찾아서 최적화
최적화된 풀이가 완전탐색과 같은 답을 내는지 검증

핵심 정리

방법	경우의 수	사용 도구
중첩 반복문	O(n^k)	for문
순열	n!	`itertools.permutations`
조합	nCr	`itertools.combinations`
부분집합	2^n	비트마스크

백트래킹 — 가지치기가 붙은 완전탐색

완전탐색에서 "이 방향은 답이 될 수 없다"고 판단되면 더 진행하지 않고 되돌아가는 기법입니다:

python

# N-Queen 문제: N×N 체스판에 N개의 퀸을 서로 공격 못하게 배치
def solve_nqueens(n):
    solutions = []
    
    def backtrack(queens, row):
        if row == n:
            solutions.append(queens[:])
            return
        
        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)
                backtrack(queens, row + 1)
                queens.pop()  # 되돌리기 (backtrack)
    
    def is_safe(queens, row, col):
        for r, c in enumerate(queens):
            if c == col or abs(r - row) == abs(c - col):
                return False
        return True
    
    backtrack([], 0)
    return solutions

print(len(solve_nqueens(8)))  # 92가지 해

8×8 체스판에서 가능한 모든 배치는 약 43억 가지이지만, 가지치기로 실제 탐색하는 경우의 수는 수천 개 수준으로 줄어듭니다.

재귀 vs 반복문 선택

python

# 재귀 — 트리 구조의 탐색에 자연스러움
def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            paths.extend(find_all_paths(graph, node, end, path))
    return paths

# 반복문 — 단순 나열에 적합
for i in range(n):
    for j in range(i + 1, n):
        check(arr[i], arr[j])

중첩 반복문은 깊이가 정해져있을 때, 재귀는 깊이가 가변적일 때 사용합니다. Python의 재귀 깊이 제한(기본 1000)에 주의합니다.

시간 제한 감각

코딩 테스트에서 시간 제한(보통 1~2초)을 맞추려면 연산 횟수를 가늠해야 합니다:

text

Python 기준 (대략적인 감각):
  10^6 연산 → ~0.1초
  10^7 연산 → ~1초
  10^8 연산 → ~10초 (시간 초과)

python

# n=10 → 2^10 = 1,024 → 완전탐색 가능
# n=20 → 2^20 = 1,048,576 → 가능하지만 빠듯
# n=30 → 2^30 = 1,073,741,824 → 시간 초과
# n! → n=10이면 3,628,800, n=12면 479,001,600

n 범위	가능한 복잡도	기법
≤ 10	O(n!)	순열 완전탐색
≤ 20	O(2^n)	부분집합/비트마스크
≤ 1,000	O(n²)	이중 for
≤ 100,000	O(n log n)	정렬 + 이진 탐색
≤ 10,000,000	O(n)	선형 탐색, 해시

입력 크기를 보고 어떤 복잡도가 통과하는지 먼저 판단하면, 완전탐색을 시도할지 바로 최적화할지 결정할 수 있습니다.

완전탐색은 "무식한 방법"이 아닙니다. 정확한 답을 보장하는 기준선이자, 더 나은 알고리즘의 출발점입니다.