📌 완전 탐색(Brute Force)과 원복(Backtracking)의 차이점

완전 탐색:
가능한 모든 경우를 전부 탐색하여 정답을 찾는 방식
백트래킹(원복):
불필요한 경우를 미리 제외하여 탐색 횟수를 줄이는 최적화 기법

---

✅ 1️⃣ 완전 탐색(Brute Force)

🔹 개념:

• 가능한 모든 경우의 수를 전부 탐색하여 답을 찾음
• 예제: 부분집합을 구할 때, 각 숫자를 "포함" or "미포함" 하는 경우를 모두 고려

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

vector<int> numbers = {1, 2, 3};  // 예제 데이터

// 모든 부분집합을 탐색하는 함수 (완전 탐색)
void bruteForce(int idx, vector<int> subset) 
{
    if (idx == numbers.size()) 
    {  // 기저 사례 (모든 원소를 확인함)
        cout << "{ ";
        for (int num : subset) cout << num << " ";
        cout << "}\n";
        return;
    }

    // 1. 현재 숫자를 포함하는 경우
    subset.push_back(numbers[idx]);
    bruteForce(idx + 1, subset);

    // 2. 현재 숫자를 포함하지 않는 경우
    subset.pop_back();  // 원복(Backtrack)
    bruteForce(idx + 1, subset);
}

int main() 
{
    vector<int> subset;
    bruteForce(0, subset);
    return 0;
}

🔹 시간 복잡도:

• N개의 원소가 있다면, 2^N개의 부분집합이 존재
• 따라서 O(2^N) 의 시간 복잡도를 가짐

---

✅ 2️⃣ 원복(Backtracking)

🔹 개념:

• 불필요한 탐색을 미리 제거하여 시간 복잡도를 줄이는 기법
• 탐색 중, 정답이 될 가능성이 없는 경우 즉시 중단
• 일반적으로 DFS + 가지치기로 사용됨

🔹 예제:

• 부분집합 중, 합이 6 이상인 경우는 탐색하지 않음 (불필요한 탐색 제거)

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

vector<int> numbers = {1, 2, 3};
int target = 6;  // 특정 조건을 만족하는 경우만 탐색

void backtracking(int idx, vector<int> subset, int sum) 
{
    if (sum >= target) return;  // 탐색 중단 (불필요한 경우 제거)

    if (idx == numbers.size()) 
    {  // 모든 원소 확인 완료
        cout << "{ ";
        for (int num : subset) cout << num << " ";
        cout << "}\n";
        return;
    }

    // 1. 현재 숫자를 포함하는 경우
    subset.push_back(numbers[idx]);
    backtracking(idx + 1, subset, sum + numbers[idx]);

    // 2. 현재 숫자를 포함하지 않는 경우
    subset.pop_back();  // 원복(Backtrack)
    backtracking(idx + 1, subset, sum);
}

int main() 
{
    vector<int> subset;
    backtracking(0, subset, 0);
    return 0;
}

🔹 시간 복잡도 감소 효과:

• 탐색 중단(Pruning) 으로 인해 O(2^N)보다 빠름
• 특정 조건에 따라 O(N!) → O(N log N) 수준으로 감소 가능

---

✅ 3️⃣ 완전 탐색 vs 백트래킹 비교

방식 탐색 방식 시간 복잡도 최적화 가능 여부

완전 탐색	모든 경우 확인	O(2^N)	❌ (최적화 없음)
백트래킹	불필요한 경우 가지치기	O(2^N) → O(N log N)	✅ (탐색 중단으로 최적화)

✅ 백트래킹은 완전 탐색을 기반으로 하지만, "불필요한 경우를 제거"하여 탐색 속도를 개선하는 방식

---

✅ 4️⃣ 결론

• 완전 탐색은 모든 경우를 고려하여 답을 찾음 (최악의 경우 매우 느림)
• 원복(백트래킹)은 가능성이 없는 경로를 미리 제거하여 탐색 속도를 개선
• 백트래킹을 잘 사용하면 O(2^N)보다 훨씬 빠르게 최적해를 찾을 수 있음

📌 🚀 더 궁금한 점 있으면 질문 주세요! 😊