🚀 재귀를 활용한 완전 탐색 vs 백트래킹 비교!

---

📌 1️⃣ 완전 탐색

"완전 탐색(Brute Force)" 방식으로 모든 경우를 확인하면서 합을 11로 나눈 나머지(mod 11)의 최댓값을 찾는 코드

---

📌 2️⃣ 코드 흐름 분석

void findMaxMod(int index, int sum) 
{
    // 🎯 모든 숫자를 확인했을 때 (모든 경우를 시도한 후)
    if (index == N) 
    {
        maxMod = max(maxMod, sum % 11);  // 최댓값 갱신
        return;
    }

    // 1️⃣ 현재 숫자를 선택하는 경우
    findMaxMod(index + 1, sum + numbers[index]);

    // 2️⃣ 현재 숫자를 선택하지 않는 경우
    findMaxMod(index + 1, sum);
}

---

📌 3️⃣ 코드 실행 과정 (예제 입력)

입력 예시 (N=4, numbers = {24, 35, 38, 40})

N = 4
numbers = {24, 35, 38, 40}

---

📌 4️⃣ 재귀 호출 과정

📍 findMaxMod(0, 0) 실행

• 첫 번째 숫자 24를 선택할지 말지 결정해야 함!

호출된 함수 선택한 숫자 현재 합 재귀 호출

findMaxMod(0, 0)	{}	0	숫자 선택 O → findMaxMod(1, 24)
findMaxMod(0, 0)	{}	0	숫자 선택 X → findMaxMod(1, 0)

---

📍 findMaxMod(1, 24) 실행

• 두 번째 숫자 35를 선택할지 말지 결정해야 함!

호출된 함수 선택한 숫자 현재 합 재귀 호출

findMaxMod(1, 24)	{24}	24	숫자 선택 O → findMaxMod(2, 59)
findMaxMod(1, 24)	{24}	24	숫자 선택 X → findMaxMod(2, 24)

---

📍 이 과정이 계속 반복되어, 2^N 개의 경우를 모두 확인

예제 입력 (N=4)인 경우,

• 총 2⁴ = 16번의 경우의 수를 탐색해야 함!

✅ 즉, 모든 경우를 다 시도하면서 최적의 mod 11 값을 찾는 방법!

---

🚀 5️⃣ 백트래킹을 사용하면 뭐가 다를까?

백트래킹(Backtracking)은 "불필요한 경우의 수를 미리 제거"하는 기법!

---

📌 6️⃣ 백트래킹 코드 (불필요한 탐색 제거)

void findMaxMod(int index, int sum) 
{
    // 🎯 만약 현재 sum이 이미 maxMod보다 작다면 더 탐색할 필요 없음!
    if (sum % 11 < maxMod) return;  

    if (index == N) 
    {
        maxMod = max(maxMod, sum % 11);
        return;
    }

    // 1️⃣ 현재 숫자를 선택하는 경우
    findMaxMod(index + 1, sum + numbers[index]);

    // 2️⃣ 현재 숫자를 선택하지 않는 경우
    findMaxMod(index + 1, sum);
}

---

📌 7️⃣ 완전 탐색 vs 백트래킹 차이

완전 탐색 백트래킹

방법	모든 경우를 탐색	불필요한 경우 제거
시간 복잡도	O(2^N)	O(2^N)보다 더 적음
불필요한 탐색	많음 (모든 경우 시도)	적음 (필요한 경우만 탐색)
최적화	X (비효율적)	O (효율적)

---

📌 8️⃣ 백트래킹의 효과

✅ 불필요한 탐색을 줄여서 실행 속도를 빠르게 함!
✅ 하지만 문제에 따라 백트래킹이 적용되지 않을 수도 있음!
✅ 경우의 수가 많아질수록 백트래킹이 훨씬 유리함!

 

 

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

int N, maxMod = 0;
int  cnt = 1;
vector<int> numbers;

// ✅ 재귀 함수: 현재 index에서 숫자를 선택하거나 선택하지 않는 방식
void findMaxMod(int index, int sum) 
{
    if (sum % 11 < maxMod) return;
    //if (maxMod == 10) return;

    // 🎯 모든 숫자를 확인했을 때, mod 11 값 업데이트
    if (index == N) 
    {
        maxMod = max(maxMod, sum % 11);
        return;
    }
    cnt++;
    //1.현재 숫자를 선택하는 경우
    findMaxMod(index + 1, sum + numbers[index]);

    //2. 현재 숫자를 선택하지 않는 경우
    findMaxMod(index + 1, sum);
}

int main() {
    // 🔹 입력 받기a
    cin >> N;
    numbers.resize(N);
    for (int i = 0; i < N; i++) 
    {
        cin >> numbers[i];
    }

    // 🚀 완전 탐색 시작 (재귀 함수 호출)
    findMaxMod(0, 0);

    // 🔹 최종 결과 출력
    cout << "가장 큰 mod 11 값: " << maxMod << endl;
    cout << "cnt : " << cnt << endl;

    return 0;
}

if (sum % 11 < maxMod) return;
이 한줄의 추가 만으로 1024번 반복이 16번으로 줄어듬