[Python] 알고리즘 개념17 - 완전 탐색(Brute Force)

 

 

🚀 1. 완전 탐색이란?

**완전 탐색(Brute Force)**은 가능한 모든 경우를 탐색하여 정답을 찾는 방법이에요.

 

💡 쉽게 이해하기

• 🔍 비밀번호 찾기: 모든 숫자 조합을 시도하는 방식
• 🎯 퍼즐 맞추기: 가능한 모든 방법을 시도하여 정답을 찾는 방식
• 🎰 로또 번호 조합: 모든 조합을 생성하여 당첨 번호를 찾는 방식

 

📌 완전 탐색의 특징

1. 모든 경우를 탐색하기 때문에 항상 정답을 보장해요.
2. 하지만 경우의 수가 많아지면 시간이 오래 걸릴 수 있어요.
3. 문제에서 입력 크기가 작을 때 주로 사용해요.

➡ 즉, 가능한 모든 방법을 하나씩 시도하는 방식이에요!

---

 

 

🚀 2. 완전 탐색의 대표적인 유형

📌 완전 탐색이 사용되는 문제 유형

 

문제 유형 예제

순열(Permutation)	특정 숫자의 모든 순서를 생성
조합(Combination)	특정 개수의 숫자를 선택하는 모든 조합
백트래킹(Backtracking)	상태를 저장하며 탐색하는 방식
비트마스킹(Bitmasking)	부분 집합을 효율적으로 탐색

➡ 완전 탐색은 다양한 문제에서 활용될 수 있어요!

---

 

 

🚀 3. 완전 탐색 구현 예제

 

 

✅ 1) 순열 (Permutation)

 

💡 문제:

주어진 숫자들의 모든 순서를 출력하세요.

 

📌 Python 코드 구현

from itertools import permutations

arr = [1, 2, 3]
perm = permutations(arr)
for p in perm:
    print(p)

➡ itertools.permutations를 사용하면 모든 순열을 쉽게 구할 수 있어요!

---

 

 

✅ 2) 조합 (Combination)

 

💡 문제:

주어진 숫자 중에서 r개의 숫자를 선택하는 모든 조합을 출력하세요.

 

📌 Python 코드 구현

from itertools import combinations

arr = [1, 2, 3, 4]
comb = combinations(arr, 2)
for c in comb:
    print(c)

➡ itertools.combinations를 사용하면 모든 조합을 쉽게 구할 수 있어요!

---

 

 

✅ 3) 백트래킹을 활용한 N-Queen 문제

 

💡 문제:

N x N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하세요.

 

📌 Python 코드 구현

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

def solve(board, row, n):
    if row == n:
        print(board)
        return
    for col in range(n):
        if is_safe(board, row, col, n):
            board[row] = col
            solve(board, row + 1, n)
            board[row] = -1

n = 4
board = [-1] * n
solve(board, 0, n)

➡ 백트래킹을 활용하면 불필요한 탐색을 줄이면서 완전 탐색을 최적화할 수 있어요!

---

 

 

🚀 4. 완전 탐색의 시간복잡도

 

📌 완전 탐색의 시간복잡도는?

문제 유형 시간복잡도

순열(Permutation)	O(n!)
조합(Combination)	O(2^n)
백트래킹(Backtracking)	O(n!)
비트마스킹(Bitmasking)	O(2^n)

 

💡 완전 탐색이 비효율적인 이유

• 경우의 수가 너무 많아지면 실행 시간이 급격히 증가해요.
• 예를 들어, n = 10일 때 n! = 3,628,800으로 매우 커져요!

 

📌 그래서 완전 탐색을 사용할 때 고려해야 할 점

• 입력 크기가 작을 때 사용해야 해요.
• 더 효율적인 알고리즘(그리디, 동적 계획법 등)이 있는지 고민해야 해요.

➡ 완전 탐색은 기본적인 접근법이지만, 최적화가 필요할 수 있어요!

---

 

 

✅ 마무리 정리

• 완전 탐색은 가능한 모든 경우를 탐색하여 정답을 찾는 방식이에요.
• 항상 정답을 보장하지만, 경우의 수가 많아지면 비효율적이에요.
• 순열, 조합, 백트래킹, 비트마스킹 등의 방법이 있어요.
• 입력 크기가 작을 때 유용하며, 더 효율적인 알고리즘을 고려해야 해요!