[알고리즘] 완전탐색 알고리즘

완전탐색(Brute Force)이란? 

가능한 모든 경우를 전부 탐색해서 정답을 찾는 알고리즘 기법

• “이게 정답일 수도 있지 않을까?” → 모든 경우를 다 해보는 방식
• 정답을 보장하지만, 느릴 수 있음
• 데이터 양이 작을 때 강력한 전략

항목	설명
💡 장점	구현 간단, 정답 보장
🐢 단점	시간 오래 걸릴 수 있음
✅ 쓸만한 경우	경우의 수가 작을 때 (ex. N ≤ 10⁴ 이하)
❌ 비추 상황	경우의 수가 너무 많을 때 (N! 또는 2^N 이상)

 

대표 문제 유형

유형	설명
모든 조합 시도	ex. 로또 번호, 숫자 자릿수 조합
모든 순열 시도	ex. 외판원 순회(TSP), 나이트 이동
부분집합 탐색	ex. 부분합, 배낭문제 (작은 입력일 때)
백트래킹	완전탐색에 가지치기를 더한 진화 버전

 

완전 탐색의 기본 개념은 "전부 해보기"이나, 여러 종류의 탐색방법이 있다.

---

완전탐색의 대표적인 종류

: 크게 5가지로 보자면 단순 BruteForse, 순열, 재귀호출, 비트마스크, BFS/DFS 가 있다.

아래의 표는 그걸 더 세세하게 나눠본것.

유형	핵심 키워드	사용 도구/예시	시간복잡도
1. 순열(permutation)	순서 중요, 중복 ❌	itertools.permutations()	O(N!) (보통 N ≤ 8 이하)
2. 조합(combination)	순서 상관없음, 중복 ❌	itertools.combinations()	O(NCr) ≈ O(2ⁿ)
3. 중복 순열(product)	순서 중요, 중복 허용	itertools.product()	O(N^R)
4. 부분집합 탐색(subset) - 비트마스크	선택하거나 말거나	비트마스크, 1 << N	O(2ⁿ)
5. 일반 수열/범위 완전탐색 (단순 Brute Force)	모든 수를 다 돌려봄	range(), 중첩 for문	O(N), O(N²), O(N³) … 상황에 따라
6. BFS / DFS 완전탐색	트리, 그래프, 맵 등 구조 탐색	deque(BFS), 재귀/스택(DFS), visited	O(V + E), O(Nᴰ)
7. 재귀 호출 기반 완전탐색	깊이 우선으로 직접 모든 경우 생성	dfs(depth) + 백트래킹 (append/pop)	보통 O(N!) 또는 O(2ⁿ)

 

* 시간 복잡도 감 잡는 기준

: N이 작으면 (N ≤ 10~15): 완전탐색 사용 가능  / N이 크면 (N ≥ 20~30): 백트래킹 or DP가 필요함

우선 완전 탐색부터 알아보고 아래에서 백트래킹을 보자.

1. 순열 (Permutation)

주어진 n개의 원소 중에서 r개를 뽑아 순서 있게 나열

from itertools import permutations

for p in permutations([1, 2, 3], 2):
    print(p)  # (1,2), (1,3), (2,1), (2,3), ...

2. 조합 (Combination)

순서는 신경 안 쓰고, r개를 뽑기만 하면 됨

from itertools import combinations

for c in combinations([1, 2, 3], 2):
    print(c)  # (1,2), (1,3), (2,3)

 

순서 상관 없이 2개만 뽑는다. (복권, 팀 나누기, 삼총사 문제 등)

 

3. 중복 순열 (Product)

중복 허용, 모든 경우의 수를 나열

from itertools import product

for p in product([0, 1], repeat=3):
    print(p)  # (0,0,0), (0,0,1), ..., (1,1,1)

 

자릿수 조합, 비밀번호 만들기, 생성자 문제 등

4. 부분집합 탐색 (Subset) - 비트마스크 탐색

n개의 원소에 대해 포함할지 말지(선택할지 말지)를 2^n 경우로 나눔

arr = [1, 2, 3]
n = len(arr)
for i in range(1 << n):  # 2^n 번 순회
    subset = []
    for j in range(n):
        if i & (1 << j):
            subset.append(arr[j])
    print(subset)

 

부분합 문제, 특정 조건을 만족하는 조합

" 1 << n " 비트 연산자로, 1을 왼쪽으로 n비트만큼 이동한다는 뜻.

1 << 3  은  8이다.
# 왜? 이진수 1 →  (3칸 비트 이동)→ 이진수 1000 => (2^3 = 8)

 

 

그래서 즉, range(1 << n)은 0부터 2ⁿ - 1까지라는 뜻이 된다.

 

n개의 원소가 있으면 부분집합의 개수는 2ⁿ 개이므로, 모든 부분집합을 순회하기 위해 사용된다.

 

5. 일반적인 수치 완전탐색

숫자 범위를 지정하고 모든 경우의 수를 다 돌림

for i in range(1000):
    for j in range(1000):
        if i * j == 123456:
            print(i, j)

---

그런데 아까 위에서,

* 시간 복잡도 감 잡는 기준

: N이 작으면 (N ≤ 10~15): 완전탐색 사용 가능  / N이 크면 (N ≥ 20~30): 백트래킹 or DP가 필요함

우선 완전 탐색부터 알아보고 아래에서 백트래킹을 보자.

라고 말했었다.

백트래킹(Backtracking)이란?

해결책으로 가는 도중에 막히게 되면, 그 지점으로 다시 돌아가서 다른 경로를 탐색.

모든 가능한 경우의 수를 탐색하지만, 막히면 돌아가므로 시간 절약됨.

완전탐색 + 가지치기(pruning) 기법
= 불필요한 탐색은 일찍 중단해서 시간 절약!

 

N자리 숫자 만들기의 예시를 들어보면,

def dfs(depth, path):
    if depth == N:
        print(path)
        return
    for i in range(10):
        if i in path:  # 중복 제거 (가지치기!)
            continue
        dfs(depth + 1, path + [i])

 

- depth == N이면 끝나고,

- i in path인 경우는 볼 필요 없으니까 넘어간다.

 

✅ 보통 DFS를 기반으로 구현한다. 한 경로를 끝까지 파고 들어갔다가, 조건에 따라 다시 돌아올 수 있으므로(재귀)

def backtrack(path):
    if 조건 만족:
        정답 저장 or 출력
        return
    for 선택 in 후보군:
        if 조건에 안 맞으면 continue  # 가지치기
        path.append(선택)
        backtrack(path)
        path.pop()  # 원상복구

 

append → 재귀 → pop