✅ 완전 탐색 (Brute Force)란? 🚀

완전 탐색 (Brute Force) 는 가능한 모든 경우를 전부 확인하여 정답을 찾는 방법
✔ "모든 경우를 다 해보자!" 라는 개념
✔ 정답을 보장하지만, 시간이 오래 걸릴 수 있음
✔ O(N!), O(2^N), O(N^2) 등의 시간 복잡도

---

📌 완전 탐색의 종류

방법 설명

1️⃣ 단순 반복문 (Simple Iteration)	for, while문을 사용하여 모든 경우 탐색
2️⃣ 재귀 함수 (Recursive Approach)	함수 호출을 통해 모든 경우 확인
3️⃣ 비트마스크 (Bitmasking)	0과 1을 활용하여 모든 경우 탐색
4️⃣ 백트래킹 (Backtracking)	가지치기를 추가한 완전 탐색
5️⃣ 순열 & 조합 (Permutation & Combination)	모든 경우를 탐색하여 최적의 경우 찾기

---

📌 예제 1: 배열에서 특정 숫자 찾기 (O(N))

배열 {3, 1, 4, 1, 5, 9, 2, 6, 5}에서 숫자 5가 있는지 찾는 코드

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

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    int target = 5;
    bool found = false;

    // 완전 탐색으로 찾기
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            found = true;
            break;
        }
    }

    if (found) cout << target << "을(를) 찾았습니다!\n";
    else cout << "찾는 숫자가 없습니다.\n";
    
    return 0;
}

✅ 시간 복잡도: O(N)

---

📌 예제 2: 1부터 100까지 모든 수의 합 구하기 (O(N))

#include <iostream>
using namespace std;

int main() {
    int sum = 0;
    for (int i = 1; i <= 100; i++) {
        sum += i;  // 모든 경우를 하나씩 더하기
    }
    cout << "1부터 100까지 합: " << sum << endl;
    return 0;
}

✅ 시간 복잡도: O(N)

---

📌 예제 3: 모든 경우의 수 탐색 (O(N^2))

배열 {1, 2, 3, 4, 5}에서 두 숫자의 합이 6이 되는 경우 찾기

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

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};

    for (int i = 0; i < arr.size(); i++) {
        for (int j = i + 1; j < arr.size(); j++) {
            if (arr[i] + arr[j] == 6) {
                cout << "두 숫자: " << arr[i] << " + " << arr[j] << " = 6\n";
            }
        }
    }
    
    return 0;
}

✅ 시간 복잡도: O(N^2)

---

📌 예제 4: 순열 (Permutation, O(N!))

배열 {1, 2, 3}의 모든 순열 출력하기

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

int main() {
    vector<int> arr = {1, 2, 3};

    do {
        for (int num : arr) cout << num << " ";
        cout << endl;
    } while (next_permutation(arr.begin(), arr.end()));

    return 0;
}

✅ 시간 복잡도: O(N!) (3개의 숫자는 3! = 6개의 경우)

---

📌 완전 탐색의 특징

✔ 장점:

• 확실한 정답을 보장
• 모든 경우를 다 체크하므로 논리적으로 단순함

✔ 단점:

• 경우의 수가 많아지면 시간이 매우 오래 걸림 (O(N!), O(2^N))
• 비효율적이므로 개선이 필요할 수도 있음 (e.g., 백트래킹, DP 활용)

---

📌 언제 완전 탐색을 사용할까?

사용 경우 이유

✅ 경우의 수가 작을 때 (N ≤ 10^5 이하)	완전 탐색으로 충분히 해결 가능
✅ 정확한 정답을 보장해야 할 때	모든 경우를 탐색하면 반드시 정답을 찾을 수 있음
✅ 더 좋은 알고리즘이 떠오르지 않을 때	완전 탐색으로 먼저 구현하고 최적화 가능

---

📌 최종 정리

탐색 유형 예제 시간 복잡도

단순 반복문	배열에서 특정 숫자 찾기	O(N)
이중 반복문	두 숫자의 합 찾기	O(N^2)
순열 탐색	모든 숫자 조합	O(N!)
비트마스크	부분집합 탐색	O(2^N)