완전 탐색

완전 탐색이란?

완전 탐색(Exhaustive Search)은 가능한 모든 경우를 하나씩 다 테스트하는 방식.
한마디로 판단하는 것이 아니라, 가능한 모든 경우를 모두 테스트하는 방식이기 때문에 한계가 있지만, 쉽고 진정한 방법입니다.

예를 들어, 비밀번호를 찾을 때 0000부터 9999까지 모든 숫자를 입력해보는 방식이 바로 완전 탐색

0000, 0001, 0002, ... 9999 (총 10,000개)

모든 경우를 시도하므로 완전 탐색(Brute Force)이라고 볼 수 있다.

특징

• 해결책이 없을 때, 가장 반대하지만 진정한 방법

• 한 번에 가능하면 모든 경우를 찾는 방식

• 복잡한 사항이 없을 때 복수 시간 제어 가능

완전 탐색의 유형 🔎

1. Brute Force(브루트 포스)

• 모든 경우를 무시하고 한가지 씩 찾아봄

2. Backtracking(백트래킹)

• 지리해진 경우는 확인하지 않고 탐색을 중단

3. BitMasking(비트마스킹)

• 0과 1을 활용하여 보복점 복수를 풀어내는 방법

4. DFS/BFS 탐색

• 그래프에서 가능한 모든 경로를 탐색

이제 완전탐색의 유형들을 코드로 하나씩 알아보자

Brute Force(브루트 포스)

# 1부터 100까지 숫자 중에서 특정 숫자 찾기 (브루트 포스 방식)
target = 37
for i in range(1, 101):
    if i == target:
        print(f"정답은 {i}!")
        break

✅ 모든 경우를 하나하나 직접 시도하는 방식
✅ 시간복잡도: O(N)

Backtracking(백트래킹)

def subset_sum(idx, total):
    if total > 100:  # 가지 치기 (불필요한 탐색 방지)
        return
    if idx == len(arr):
        print(total)
        return
    subset_sum(idx + 1, total + arr[idx])  # 선택하는 경우
    subset_sum(idx + 1, total)  # 선택하지 않는 경우

✅ 불필요한 경우를 미리 제외하여 탐색 범위 줄이기
✅ 시간복잡도: O(2^N)

Bitmasking(비트마스킹)

arr = [1, 2, 3]
n = len(arr)
for i in range(1 << n):  # 2^N개의 부분 집합을 탐색
    subset = [arr[j] for j in range(n) if (i & (1 << j))]
    print(subset)

✅ 모든 부분 집합을 빠르게 탐색
✅ 시간복잡도: O(2^N)

DFS/BFS 탐색 → 그래프에서 모든 경로 탐색

def dfs(graph, node, visited):
    visited[node] = True
    print(node, end=' ')
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

✅ 그래프 탐색에 적합한 완전 탐색 방법
✅ 시간복잡도: O(V+E) (정점+간선)

완전 탐색의 시간복잡도 분석

✅ O(N!), O(2^N) 알고리즘은 입력 크기가 클 경우 실행 불가능
✅ N ≤ 10까지는 완전 탐색 가능, N > 20이면 다른 방법 필요 🚀

완전 탐색을 최적화하는 방법

완전 탐색을 그대로 쓰면 비효율적이기 때문에 최적화 기법을 적용해야 한다

가지 치기 (Pruning) → 불필요한 탐색 방지

✔ 불가능한 경우는 미리 배제하여 탐색 시간 절약 (예: N-Queen)

if not is_valid(state):
    return  # 더 이상 탐색할 필요 없음

메모이제이션 (Memoization) → 중복 계산 방지

✔ 이미 계산한 값을 저장하여 중복 계산을 방지 (예: 피보나치)

cache = {}
def fib(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

실전문제 예제

✔ 비밀번호 크래킹 (Brute Force)

from itertools import product

digits = "0123456789"
length = 3  # 비밀번호 길이
password = "123"  # 실제 비밀번호 (예제)

for attempt in product(digits, repeat=length):
    attempt = "".join(attempt)
    if attempt == password:
        print(f"비밀번호 찾음: {attempt}")
        break

✅ 시간복잡도: O(10^M) → M이 커지면 시간이 오래 걸림!

✔ N-QUEEN (Backtracking)

def is_safe(queens, row, col):
    for r in range(row):
        if queens[r] == col or abs(queens[r] - col) == abs(r - row):
            return False
    return True

def solve_n_queens(n, row=0, queens=[]):
    if row == n:
        print(queens)
        return
    for col in range(n):
        if is_safe(queens, row, col):
            solve_n_queens(n, row + 1, queens + [col])

n = 4  # 체스판 크기
solve_n_queens(n)

✅ 시간복잡도: O(N!) → N이 클수록 매우 느려짐!

✔ 부분 집합 구하기 (Bitmasking)

arr = [1, 2, 3]
n = len(arr)

for i in range(1 << n):  # `2^N`개의 경우의 수
    subset = [arr[j] for j in range(n) if i & (1 << j)]
    print(subset)

✅ 시간복잡도: O(2^N) → N이 크면 비효율적!

✔ 미로 탈출 (BFS)

from collections import deque

maze = [
    [1, 0, 1, 1, 1],
    [1, 1, 1, 0, 1],
    [0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1]
]
n, m = len(maze), len(maze[0])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    queue = deque([(0, 0, 1)])  # (x, y, 이동 거리)
    while queue:
        x, y, dist = queue.popleft()
        if x == n - 1 and y == m - 1:
            return dist  # 목적지 도착 시 최소 거리 반환
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
                queue.append((nx, ny, dist + 1))
                maze[nx][ny] = 0  # 방문 처리
    return -1  # 도착 불가능

print(bfs())  # 최단 거리 출력

✅ 시간복잡도: O(V+E) → 미로 크기에 따라 효율적!