인프런 커뮤니티 질문&답변
작성한 질문수
mod11 개념문제 백트래킹 질문드립니다.
작성
·
203
0
큰돌님 안녕하세요.
3주차 문제들을 풀던 중 의문점이 생겨서 질문드립니다.
3주차 개념강의 때 합을 mod 11한 숫자 중 가장 큰 수를 구하는 예시문제가 있었습니다.
이 문제를 아래와 같은 방법으로 재귀를 통해 각 숫자별로 더할지 말지로 나눠서 숫자가 {1,2,3}인 경우는 총 경우의 수가 8이 된다고
말씀하셨습니다.
go(idx + 1, sum + v[idx]);
go(idx + 1, sum);
그런데 3주차 문제들을 풀던 도중 백트래킹을 쓰는 경우와 이렇게 재귀로 현재 위치를 하나씩 증가시켜가며 포함하는지 안하는지를 체크해가며 완전탐색을 돌리는 경우가 같은 경우가 아닌가 하는 의문점이 들었습니다(둘 다 모든 경우를 따지는 것이기 때문입니다).
그래서 개념강의 예시문제를 다시 백트래킹으로 풀어보았는데 {1,2,3}인 경우에서 8번의 경우를 따져야 하는데 경우의 수를 4번만 도출해는 것을 확인하였습니다. 아래는 백트래킹으로 구현한 mod 11 문제입니다.
#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];
}
// 설명해주신 방식
// 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';
}코드를 하나하나 디버깅해가며 체크해보면서 왜 4번만 경우를 구하게 되는지는 알게 되었는데,
개념적으로 백트래킹이라는 개념이 모든 경우의 수를 구하는 것이고, 기존에 풀었던 방법인 idx를 증가시키면서 해당 위치의 숫자를 더할지 말지를 구하는 것도 모든 경우의 수를 구하는 것이라서 두 경우의 문제 접근할 때의 사고방식이 같다고 생각하는데 왜 백트래킹은 안되는 것인가요? 두 경우의 차이점이 너무 헷갈립니다 ㅠㅠ
답변 1
0
안녕하세요 덕용님 ㅎㅎ
그런데 3주차 문제들을 풀던 도중 백트래킹을 쓰는 경우와 이렇게 재귀로 현재 위치를 하나씩 증가시켜가며 포함하는지 안하는지를 체크해가며 완전탐색을 돌리는 경우가 같은 경우가 아닌가 하는 의문점이 들었습니다(둘 다 모든 경우를 따지는 것이기 때문입니다).
>> 백트래킹은 모든 경우의 수를 따지는 것이 아니라 휴리스틱으로 일부분의 경우의 수를 가지치기 합니다.
void go(int idx, int sum){
if(idx == n){
ret = max(ret, sum % mod);
cnt++;
return;
}이 코드는 백트래킹이라고 볼 수 없습니다.
idx == n까지의 모든 경우의수를 돌리는 코드입니다.
이 부분이 추가되어야 백트래킹이라고 할 수 있는데요.
void go(int idx, int sum){
if(ret == 10) return;
바로 MOD 11을 했을 때 최대의 숫자는 10이기 때문에 이부분에 대해 추가로 경우의 수를 찾을 필요가 없게
"가지치기"가 되기 때문입니다.
개념적으로 백트래킹이라는 개념이 모든 경우의 수를 구하는 것이고, 기존에 풀었던 방법인 idx를 증가시키면서 해당 위치의 숫자를 더할지 말지를 구하는 것도 모든 경우의 수를 구하는 것이라서 두 경우의 문제 접근할 때의 사고방식이 같다고 생각하는데 왜 백트래킹은 안되는 것인가요?
>> 백트래킹은 모든 경우의 수를 구하는게 아닙니다. 가지치기가 들어가야 합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 덕용님 ㅎㅎ
하지만 제가 정말 의문이었던 부분은 백트래킹이 가지치기를 추가한다고 쳐도 가장 메인이 되는 로직 부분의 동작은 값을 더해주며 나아가고, 다시 돌아와서 더해준 값을 빼주고 다시 다른 경로로 탐색해가는 이런 형태의 흐름으로 가는 것 아닌가요?
>> 네 맞습니다.
그래서 저는 "백트래킹에서 가지치기를 빼면 모든 경우의 수를 구하는 것과 동일하다"
>> 네 맞습니다.
그러면 제가 처음에 질문할 때 드린 코드가 모든 경우의 수를 구하는 게 맞지 않나요?
>> 음.. 근데 해당 코드는 해당 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 전체 중 몇가지를 고르는 문제와 같이 "무조건 첫번째(경로 문제에서는 첫 지점 고정, 몇가지를 고르는 경우 문제에서는 무조건 처음 한가지를 고르고 다음 순서로 넘어가는 것)를 포함"하는 상황
이런 상황별로 완전탐색과 백트래킹을 푸는 경우가 나뉘는 걸로 이해되었는데 맞을까요?
안녕하세요 큰돌님.
가지치기가 백트래킹이라는 것은 이해하였습니다. 감사합니다.
하지만 제가 정말 의문이었던 부분은 백트래킹이 가지치기를 추가한다고 쳐도 가장 메인이 되는 로직 부분의 동작은 값을 더해주며 나아가고, 다시 돌아와서 더해준 값을 빼주고 다시 다른 경로로 탐색해가는 이런 형태의 흐름으로 가는 것 아닌가요? (0,0) -> (2,2) 로 가는 모든 경로를 구할 때처럼요. 아래 코드가 제가 생각하는 가장 메인이 되는 로직 부분입니다. 선생님께서 말씀하신 것은 백트래킹은 가지치기이다라고 하셨습니다. 그래서 저는 "백트래킹에서 가지치기를 빼면 모든 경우의 수를 구하는 것과 동일하다" 라고 이해가 되었는데... 그러면 제가 처음에 질문할 때 드린 코드가 모든 경우의 수를 구하는 게 맞지 않나요?