완전탐색

완전 탐색(Brute Force)

완전 탐색(Brute Force)이란 가능한 모든 경우를 하나씩 탐색하여 정답을 찾는 알고리즘이다.
즉, 문제에서 주어진 조건을 만족하는 값을 찾을 때 모든 경우를 하나씩 검토하여 해답을 찾는 방식이다.

---

1. 완전 탐색의 핵심 개념

• 모든 경우의 수를 시도하면서 답을 찾는다.
• 시간 복잡도는 일반적으로 크지만, 가능한 경우의 수가 적을 경우 유용하다.
• 경우의 수를 줄일 수 있다면, 가지치기(Pruning) 기법을 활용한다.

---

2. 완전 탐색을 사용하는 경우

✅ 모든 경우의 수가 적을 때 (N ≤ 10^4 이하)
✅ 문제를 해결하는 더 효율적인 방법이 없을 때
✅ 정확한 정답을 보장해야 할 때

---

3. 완전 탐색 방법

(1) 단순한 반복문을 활용한 방법

• 작은 범위의 문제에서는 단순 반복문으로 모든 경우를 직접 탐색 가능하다.

# 1부터 100까지 숫자 중에서 특정 수 x를 찾는 완전 탐색
def brute_force_search(x):
    for i in range(1, 101):  # 1부터 100까지 검사
        if i == x:
            return f"{x} 찾음!"
    return "못 찾음!"

print(brute_force_search(25))  # 25 찾음!

시간 복잡도: O(N) (100개 검사)

---

(2) 중첩 반복문을 활용한 방법

• 두 개 이상의 조건을 고려해야 할 때, 모든 조합을 검사하는 방식이다.

# 두 숫자의 합이 10이 되는 쌍 찾기
def find_pairs(arr):
    pairs = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):  # 중복 방지를 위해 i+1부터 탐색
            if arr[i] + arr[j] == 10:
                pairs.append((arr[i], arr[j]))
    return pairs

print(find_pairs([1, 2, 3, 7, 8, 9, 5]))  # [(3, 7), (2, 8), (1, 9)]

⏱️ 시간 복잡도: O(N^2) (모든 쌍을 확인)

---

(3) 재귀를 활용한 완전 탐색

• DFS(깊이 우선 탐색) 방식으로 모든 가능한 경우를 탐색할 때 사용한다.

# 숫자 리스트에서 가능한 모든 조합 출력
def generate_subsets(arr, index=0, subset=[]):
    if index == len(arr):
        print(subset)  # 현재 부분 집합 출력
        return
    
    # 현재 원소를 포함하지 않는 경우
    generate_subsets(arr, index + 1, subset)
    
    # 현재 원소를 포함하는 경우
    generate_subsets(arr, index + 1, subset + [arr[index]])

print("모든 부분 집합:")
generate_subsets([1, 2, 3])

출력:

[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

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

---

4. 완전 탐색을 활용한 대표적인 문제

(1) N! 가지 경우를 모두 탐색해야 하는 문제

• 예제: N!개의 경우의 수가 존재하는 순열(Permutation) 문제 ```python from itertools import permutations

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

출력:

(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)

**시간 복잡도: `O(N!)`**

---

### **(2) 특정 조건을 만족하는 (w, h) 쌍 찾기 (카펫 문제)**
```python
def solution(brown, yellow):
    total = brown + yellow

    for h in range(1, int(total ** 0.5) + 1):
        if total % h == 0:  # h가 total의 약수인지 확인
            w = total // h  # w 계산
            if w >= h and (2 * w + 2 * h - 4) == brown:
                return [w, h]

⏱️ 시간 복잡도: O(√N)

---

5. 완전 탐색의 시간 복잡도 정리

| 탐색 방식 | 경우의 수 예시 | 시간 복잡도 | |—|—|—| | 단순 반복문 | 최대 10^4개 이하의 데이터 탐색 | O(N) | | 중첩 반복문 | 모든 두 개 조합 검사 | O(N^2) | | 3중 반복문 | 세 개 조합 검사 | O(N^3) | | 순열 (모든 순서 탐색) | N! 개 탐색 | O(N!) | | 부분 집합 탐색 | 2^N 개 탐색 | O(2^N) | | 약수 기반 탐색 | 최대 √N 개 탐색 | O(√N) |

---

정리

✅ 완전 탐색은 가능한 모든 경우를 직접 탐색하는 기법이다.
✅ 경우의 수가 많아질수록 시간 복잡도가 기하급수적으로 증가할 수 있다.
✅ 가능하면 가지치기(Pruning), 수학적 최적화, DP, 그리디 등을 사용하여 최적화해야 한다.
✅ 하지만 N이 작을 경우 가장 직관적이고 구현하기 쉬운 방법이다.

즉, “완전 탐색은 언제나 정확한 답을 찾을 수 있지만, 효율성을 고려해야 한다!”