22. 완전 탐색(Brute Force) 알고리즘: 가능한 모든 경우의 수를 탐색하는 기법

완전 탐색(Brute Force) 알고리즘은 가능한 모든 솔루션을 체계적으로 탐색하여 최적의 결과를 찾는 접근 방식이다.
이 방식은 정확한 솔루션을 보장하지만, 시간 복잡도가 높아 비효율적일 수 있다는 단점이 있다.

---

📌 1. 완전 탐색(Brute Force) 알고리즘 개념

✔ 정의:

모든 가능한 경우의 수를 하나씩 생성하고 평가하여 최적의 솔루션을 찾는 방식

✔ 특징:

• 정확한 솔루션 보장 (단, 계산량이 많을 경우 비효율적)
• 검색 공간 크기가 작을 때 효과적
• 순열(Permutation), 조합(Combination) 문제에 자주 사용
• 백트래킹(Backtracking)과 함께 사용하여 탐색 최적화 가능

✔ 적용 분야:

• 작은 입력 크기의 문제
• 최적화 문제에서 기준 솔루션(Benchmark) 설정
• 모든 경우를 확인해야 하는 문제

---

📌 2. 완전 탐색의 기본 과정

1️⃣ 후보 생성

• 문제에 대한 모든 가능한 후보 솔루션을 생성
• 순열, 조합, 부분집합 등 다양한 방식으로 생성

2️⃣ 후보 평가

• 각 후보가 문제의 조건을 만족하는지 평가

3️⃣ 최상의 솔루션 추적

• 최적화 문제인 경우 가장 좋은 해를 저장

4️⃣ 모든 후보 반복

• 가능한 모든 후보를 평가할 때까지 위 과정을 반복

5️⃣ 최종 솔루션 반환

• 찾은 최적의 솔루션을 반환

---

📌 3. 완전 탐색 알고리즘 예제

📌 예제 1: 부분집합 중 최대 합 찾기

#include <iostream>
#include <vector>
using namespace std;

vector<int> exhaustiveSearch(vector<int>& nums) {
    int n = nums.size();
    int maxSum = 0;
    vector<int> maxSubset;

    // 모든 부분집합을 탐색 (2^n 개의 경우)
    for (int i = 1; i < (1 << n); i++) {
        vector<int> subset;
        int subsetSum = 0;

        // 현재 i의 이진 표현을 기반으로 부분집합 생성
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) { // j번째 비트가 1이면 선택
                subset.push_back(nums[j]);
                subsetSum += nums[j];
            }
        }

        // 최대 합 업데이트
        if (subsetSum > maxSum) {
            maxSum = subsetSum;
            maxSubset = subset;
        }
    }

    return maxSubset;
}

int main() {
    vector<int> nums = {1, 3, 2, 4};
    vector<int> result = exhaustiveSearch(nums);

    cout << "최대 합 부분집합: { ";
    for (int num : result) cout << num << " ";
    cout << "}\n";
}

✔ 설명:

• nums = {1, 3, 2, 4}의 모든 부분집합을 탐색
• 각 부분집합의 합을 계산하고 최대 합을 가지는 부분집합을 선택
• 시간 복잡도: O(2^n) → 지수적 증가

---

📌 예제 2: 순열 생성 (모든 가능한 순서 나열)

#include <iostream>
#include <vector>
using namespace std;

void generatePermutations(vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& results) {
    if (current.size() == nums.size()) {
        results.push_back(current);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            current.push_back(nums[i]);
            generatePermutations(nums, used, current, results);
            current.pop_back();
            used[i] = false;
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> results;
    vector<bool> used(nums.size(), false);
    vector<int> current;

    generatePermutations(nums, used, current, results);

    cout << "모든 순열:\n";
    for (auto& perm : results) {
        cout << "{ ";
        for (int num : perm) cout << num << " ";
        cout << "}\n";
    }
}

✔ 설명:

• nums = {1, 2, 3}의 모든 순열을 생성
• O(n!)의 시간 복잡도를 가지므로 크기가 커지면 실행 시간이 길어짐

---

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

📌 입력 크기 증가 시 성능

입력 크기 n 가능한 경우의 수 O(2^n) 실행 가능 여부

10	1,024	✅ 빠름
20	1,048,576	⚠ 가능하지만 느림
30	1,073,741,824	❌ 비효율적
40	≈1012\approx 10^{12}	❌ 매우 비효율적

💡 완전 탐색은 보통 n ≤ 20일 때 현실적으로 실행 가능

---

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

1️⃣ 백트래킹(Backtracking)

• 불가능한 경로를 조기에 제거하여 탐색 속도 향상
• 예: N-Queen 문제, 순열 생성 문제

2️⃣ 가지치기(Pruning)

• 불필요한 탐색을 건너뛰어 연산량 감소
• 예: 최소 비용 문제에서 현재 비용이 이미 최솟값을 초과하면 탐색 중단

3️⃣ 분기 한정(Branch & Bound)

• 최적해를 찾을 가능성이 없는 분기를 미리 제거
• 예: 외판원 문제(TSP)에서 최소 비용보다 큰 경로 제거

4️⃣ 동적 프로그래밍(DP)과 결합

• 같은 부분 문제를 여러 번 계산하지 않도록 캐싱
• 예: 피보나치 수열 계산, 배낭 문제

---

📌 6. 결론: 완전 탐색은 언제 사용해야 할까?

✅ 완전 탐색이 적절한 경우

• 입력 크기 n이 작을 때 (n ≤ 20 정도)
• 정확한 해를 보장해야 할 때
• 다른 최적화 기법이 적용되기 어려운 경우

🚨 완전 탐색을 피해야 할 경우

• n이 클 때 (n > 30 이상이면 비효율적)
• 제한된 시간 내에 최적해가 필요할 때
• 탐색 공간이 너무 커서 현실적으로 계산 불가능할 때

📢 "완전 탐색은 정확한 해를 찾을 수 있지만, 입력 크기가 크다면 백트래킹, DP, 가지치기 등의 기법과 결합해야 한다!" 🚀