mod11 개념문제 백트래킹 질문드립니다.

안녕하세요 큰돌님.
가지치기가 백트래킹이라는 것은 이해하였습니다. 감사합니다.
하지만 제가 정말 의문이었던 부분은 백트래킹이 가지치기를 추가한다고 쳐도 가장 메인이 되는 로직 부분의 동작은 값을 더해주며 나아가고, 다시 돌아와서 더해준 값을 빼주고 다시 다른 경로로 탐색해가는 이런 형태의 흐름으로 가는 것 아닌가요? (0,0) -> (2,2) 로 가는 모든 경로를 구할 때처럼요. 아래 코드가 제가 생각하는 가장 메인이 되는 로직 부분입니다. 선생님께서 말씀하신 것은 백트래킹은 가지치기이다라고 하셨습니다. 그래서 저는 "백트래킹에서 가지치기를 빼면 모든 경우의 수를 구하는 것과 동일하다" 라고 이해가 되었는데... 그러면 제가 처음에 질문할 때 드린 코드가 모든 경우의 수를 구하는 게 맞지 않나요?

    for(int i = idx; i < n; i++){
        sum += v[i];
        go(i + 1, sum);
        sum -= v[i];
    }

안녕하세요 덕용님 ㅎㅎ

하지만 제가 정말 의문이었던 부분은 백트래킹이 가지치기를 추가한다고 쳐도 가장 메인이 되는 로직 부분의 동작은 값을 더해주며 나아가고, 다시 돌아와서 더해준 값을 빼주고 다시 다른 경로로 탐색해가는 이런 형태의 흐름으로 가는 것 아닌가요?

>> 네 맞습니다.

그래서 저는 "백트래킹에서 가지치기를 빼면 모든 경우의 수를 구하는 것과 동일하다"

>> 네 맞습니다.

그러면 제가 처음에 질문할 때 드린 코드가 모든 경우의 수를 구하는 게 맞지 않나요?

>> 음.. 근데 해당 코드는 해당 idx에서 무조건 sum을 더해서 idx를 넘기기 때문에 모든 경우의 수라고 볼 수 없습니다.

다음과 같이 어떤 idx에서 sum을 추가하는 경우의 수 또는 추가하지 않는 경우의 수 식의 코드가 추가가 되어야 모든 경우의 수라고 볼 수 있습니다.

go(idx + 1, sum + v[idx]);
go(idx + 1, sum);

감사합니다.

아!! 선생님 말씀 듣고 계속 손으로 흐름 따라가보면서 반복하다보니 이해가 되었습니다.
위 코드대로 하면 idx를 넘어갈 때마다 더해주는 꼴이 되고 포함하지 않는 경우가 없군요.
설명 감사드립니다. ㅎㅎ

덕용님 제가 잘못 답변 드린 부분이 있어서 답변을 다시 드리겠습니다.

음.. 근데 해당 코드는 해당 idx에서 무조건 sum을 더해서 idx를 넘기기 때문에 모든 경우의 수라고 볼 수 없습니다.

>>

이 답변을 이렇게 정정하겠습니다.

해당 코드는 해당 idx에서 무조건 sum을 더해서 idx를 넘기며 for문으로 i번째를 추가하는 경우의 수를 확인합니다. 그래서 거의 모든 수를 탐색한다고 볼 수 있습니다. 0, 1, 2 .. 이거나 0, 2 이런식으로 sum을 더해가니까요.

다만, 0번째의 요소는 무조건 더하므로.

모든 경우의 수라고 볼 수 없습니다.

덕용님의 코드를 실행하면

10

512

이렇게 되는데

이는 0번째 요소가 무조건 더해지기 때문에 그렇습니다. 0번째 요소가 더해지지 않는 경우의수가 있어야 1024가 되는데요.

이 코드를. 제가 말씀드린.

go(idx + 1, sum + v[idx]);
go(idx + 1, sum);

이렇게 아예 바꾸시거나.

이렇게 해주시면 됩니다.

#include<bits/stdc++.h>
using namespace std;
const int mod = 11;
int n, temp, cnt, ret;
vector<int> v;   

void go(int idx, int sum){
	if(idx == n){
        ret = max(ret, sum % mod);
		cnt++;
		return;
	}

    for(int i = idx; i < n; i++){
        sum += v[i];
        go(i + 1, sum);
        sum -= v[i];
        if(idx == 0){
            go(i + 1, sum);
        }
    }

    // 설명해주신 방식
    // go(idx + 1, sum + v[idx]);
    // go(idx + 1, sum);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){ 
       cin >> temp;
       v.push_back(temp);
    }
    go(0, 0);
    cout << ret << '\n';
    cout << cnt << '\n';
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

선생님 추가 답변을 이제 봤습니다.

선생님이 추가로 답변해주신 답변에서 "idx 0인 경우를 포함하지 않는 경우는 체크하지 않게 되기 때문"이라는 부분을 읽고 깨우친 것 같습니다. 완전탐색과 백트래킹을 사용하는 경우의 차이를 알게 된 것 같습니다. 제가 이해하기로는

완전탐색 -> 해당 상황마다 이 경우를 포함하는지 안하는지를 전부 따져가며 경우를 모두 구함

백트래킹 -> 한 지점이 고정이고 그 지점부터 목적지까지 가는 모든 경로 or 전체 중 몇가지를 고르는 문제와 같이 "무조건 첫번째(경로 문제에서는 첫 지점 고정, 몇가지를 고르는 경우 문제에서는 무조건 처음 한가지를 고르고 다음 순서로 넘어가는 것)를 포함"하는 상황

이런 상황별로 완전탐색과 백트래킹을 푸는 경우가 나뉘는 걸로 이해되었는데 맞을까요?