15강. 완전 탐색 | 코딩 테스트 합격 알고리즘 30강 · 중급 — 누구나패스

🎯 학습 목표

이 강을 마치면 완전 탐색(브루트포스)이 언제 정답인지 판단할 수 있습니다. 그리고 순열·조합·부분집합·중복순열의 경우의 수를 계산하고, itertools로 직접 구현 없이 생성할 수 있게 됩니다.

완전 탐색은 초보자에게 "무식한 방법"으로 오해받지만, 입력이 작으면 가장 확실하고 빠르게 통과하는 풀이입니다. 2강에서 배운 입력 범위 역산이 여기서 결정적으로 쓰입니다.

💡 완전 탐색이 정답인 조건

완전 탐색은 가능한 모든 경우를 만들어 보고 조건에 맞는 것을 고르는 방법입니다. 판단 기준은 하나입니다. "경우의 수가 감당 가능한가."

경우의 수 공식과 폭발 속도

  n개에서 r개를 뽑는 경우

   순열      nPr   순서 O, 중복 X    n × (n-1) × ... × (n-r+1)
   조합      nCr   순서 X, 중복 X    nPr / r!
   중복순열  nΠr   순서 O, 중복 O    n^r
   부분집합         각 원소를 넣거나 안 넣거나   2^n

  n이 커질 때 (전체를 나열할 때)

   n     2^n (부분집합)      n! (순열)
   ───────────────────────────────────────
   10          1,024            3,628,800
   15         32,768      1,307,674,368,000
   20      1,048,576   약 2.4 × 10^18
   25     33,554,432   사실상 불가능
   30  1,073,741,824   사실상 불가능

  ▲ 실무 감각 (2강의 범위 역산)
    n ≤ 10 정도  → n! 도 시도해 볼 만하다
    n ≤ 20~25    → 2^n 을 노려 본다
    n ≥ 30       → 완전 탐색은 포기. 다른 전략을 찾는다

  ▲ 문제에 "n ≤ 20" 이라고 적혀 있다면
    출제자가 완전 탐색을 기대한다는 강한 신호다.
    괜히 어려운 알고리즘을 찾을 필요가 없다.

  ▲ 반대 신호
    "n ≤ 100,000" 인데 완전 탐색이 떠올랐다면
    그 방향은 접어야 한다.

완전 탐색을 쓸 때는 경우의 수를 먼저 계산하는 습관이 중요합니다. 코드를 다 짜고 나서 시간 초과를 만나는 것보다, 시작 전에 곱셈 한 번으로 가능성을 확인하는 편이 훨씬 빠릅니다.

📖 네 가지 생성 방식

파이썬 itertools는 네 가지를 모두 제공합니다. 직접 구현하지 않고 쓰는 것이 정석입니다.

함수	생성하는 것	예: [1,2,3]에서 2개	개수
`permutations(a, r)`	순열	12 13 21 23 31 32	6
`combinations(a, r)`	조합	12 13 23	3
`product(a, repeat=r)`	중복순열	11 12 13 21 ... 33	9
`combinations_with_replacement(a, r)`	중복조합	11 12 13 22 23 33	6

어떤 것을 쓸지 고르는 법

  "순서가 의미 있는가?"
       │
       ├─ 예 (ABC 와 CBA 가 다름)
       │    │
       │    ├─ 같은 것을 또 뽑을 수 있나?
       │    │    ├─ 아니오 → permutations
       │    │    └─ 예     → product(repeat=r)
       │
       └─ 아니오 (ABC 와 CBA 가 같음)
            │
            ├─ 같은 것을 또 뽑을 수 있나?
            │    ├─ 아니오 → combinations
            │    └─ 예     → combinations_with_replacement

  대표 상황
   · 줄 세우기, 암호 만들기        → 순열
   · 팀 뽑기, 메뉴 고르기          → 조합
   · 자물쇠 번호, 각 칸에 값 채우기 → 중복순열
   · 부분집합 전체                 → product([0,1], repeat=n)
                                     또는 combinations 를 r=0..n 반복

  ▲ itertools 함수들은 '제너레이터'를 돌려준다
    전부 메모리에 만들지 않고 하나씩 꺼내 준다.
    n이 커도 메모리가 터지지 않는다.
    다만 '시간'은 여전히 경우의 수만큼 걸린다.

💻 실전 예제 — 완전 탐색 세 가지

from itertools import permutations, combinations, product


def best_team(scores, k):
    """k명을 골라 점수 합이 최대가 되는 조합 → C(n, k) 개 탐색"""
    best = None
    best_sum = float("-inf")
    for team in combinations(range(len(scores)), k):
        total = sum(scores[i] for i in team)
        if total > best_sum:
            best_sum = total
            best = team
    return best, best_sum


def count_valid_codes(digits, length, forbidden):
    """digits 로 만든 length 자리 코드 중 금지 문자열이 없는 개수"""
    count = 0
    for combo in product(digits, repeat=length):
        code = "".join(combo)
        if forbidden not in code:
            count += 1
    return count


def min_route(dist, start):
    """모든 도시를 한 번씩 방문하는 최소 거리 → (n-1)! 탐색"""
    n = len(dist)
    others = [i for i in range(n) if i != start]
    best = float("inf")
    for order in permutations(others):
        total = 0
        current = start
        for nxt in order:
            total += dist[current][nxt]
            current = nxt
            if total >= best:        # 가지치기: 이미 초과면 중단
                break
        else:
            total += dist[current][start]   # 출발지로 복귀
            best = min(best, total)
    return best


print(best_team([10, 40, 30, 20], 2))          # ((1, 2), 70)
print(count_valid_codes("012", 3, "00"))        # 22
matrix = [[0, 10, 15], [10, 0, 35], [15, 35, 0]]
print(min_route(matrix, 0))                     # 60

코드를 줄 단위로 보겠습니다.

combinations(range(len(scores)), k) — 값이 아니라 인덱스를 조합합니다. 같은 점수가 여러 개일 때 서로 다른 사람으로 구분하기 위해서입니다.
sum(scores[i] for i in team) — 제너레이터 표현식입니다. 리스트를 만들지 않고 바로 합을 구해 메모리를 아낍니다.
product(digits, repeat=length) — 각 자리에 모든 문자를 넣어 보는 중복순열입니다. 3진수 3자리이므로 27가지가 나옵니다.
"".join(combo) — product는 튜플을 주므로 문자열로 합칩니다(4강).
if total >= best: break — 가지치기(pruning)입니다. 이미 최선보다 나쁘면 끝까지 가 볼 필요가 없습니다. 완전 탐색의 비용을 실질적으로 크게 줄이는 기법이고, 16강 백트래킹의 핵심입니다.
else: — for에 붙은 else입니다. 파이썬 고유 문법으로, break 없이 반복이 끝났을 때만 실행됩니다. 가지치기로 중단된 경로를 자연스럽게 걸러 냅니다.
float("inf") — 최솟값을 구할 때의 초기값입니다. 14강의 -inf와 짝입니다.

min_route는 외판원 문제(TSP)의 완전 탐색 버전입니다. 복잡도가 O(n!)이므로 n이 10만 넘어도 감당하기 어렵습니다. 그래서 실제 문제에서는 n을 작게 제한하거나 DP를 결합한 풀이를 요구합니다.

⚠️ 자주 하는 실수

첫째, 경우의 수를 계산하지 않고 코드부터 씁니다. n이 25인데 순열을 돌리면 절대 끝나지 않습니다. 시작 전에 곱셈 한 번으로 확인하세요.

둘째, 순열과 조합을 헷갈립니다. "팀을 뽑는다"인데 순열을 쓰면 같은 팀을 r!번 중복해서 세게 됩니다. "순서가 의미 있는가"를 먼저 물으세요.

셋째, list()로 전부 펼칩니다. list(permutations(...))는 모든 경우를 메모리에 만듭니다. 개수가 크면 메모리가 터집니다. 바로 반복문으로 소비하세요.

넷째, 가지치기를 안 합니다. 완전 탐색이라도 "이 경로는 이미 답이 될 수 없다"는 판단이 서면 즉시 중단해야 합니다. 이론상 복잡도는 그대로여도 실제 실행 시간은 크게 줄어듭니다.

다섯째, 중복 원소를 처리하지 않습니다. 입력에 같은 값이 있으면 permutations가 겉보기에 같은 결과를 여러 번 만듭니다. 결과를 집합에 담거나 미리 정렬 후 건너뛰는 처리가 필요합니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	완전 탐색은 경우의 수가 감당되면 정답
2	n ≤ 10 → n!, n ≤ 20~25 → 2ⁿ
3	작은 입력 범위는 완전 탐색 신호
4	순서가 의미 있으면 순열, 아니면 조합
5	`itertools`로 직접 구현 없이
6	`list()`로 펼치지 말고 바로 소비
7	가지치기로 실제 시간을 줄인다

지금 해 볼 것은 min_route에서 가지치기 break를 지우고 도시 수를 8개쯤으로 늘려 시간을 비교하는 것입니다. 같은 O(n!)인데도 실행 시간이 크게 달라지는 것을 확인할 수 있습니다.

다음 16강 「백트래킹」에서는 가지치기를 전략으로 끌어올립니다. 모든 경우를 만들고 나서 거르는 것이 아니라, 만드는 도중에 가망 없는 가지를 잘라 탐색 공간 자체를 줄이는 방법을 다루겠습니다.

완전 탐색

🎯 학습 목표

💡 완전 탐색이 정답인 조건

📖 네 가지 생성 방식

💻 실전 예제 — 완전 탐색 세 가지

⚠️ 자주 하는 실수

📝 핵심 요약 + 다음 강 예고

📚 참고 자료

관련 주제

코딩 테스트 합격 알고리즘 30강

댓글