인프런 커뮤니티 질문&답변

안녕하세요 찬호님 ㅎㅎ

저는 다음과 같이 코드를 작성을 했는데 전역변수를 사용하지 않은 코드에서 백트래킹조건을 어디에 적어주어야 하는지 알 수 없어서 질문드립니다.

>> 백트래킹 조건은 기저사례 위쪽 또는 바로 아래쪽에 적어주시면 됩니다.

이를 통해 함수의 메인로직이 실행되지 않게끔 하는게 포인트입니다.

그리고 제가 재귀함수에 익숙치 않은 상태인데 재귀함수를 학습하는 방법에 대해서도 알려주실 수 있으신가요? 제가 부족해서 교안이나 강의에 해주신 설명으로는 이해하는데 어려움을 겪고 있습니다. 답변 감사합니다.

>> 음.. 일단 손코딩으로 함수의 흐름을 한번 그려보시는게 좋을 거 같습니다. 빈 종이에다가 함수가 이렇게 호출(매개변수는 변경)을 그리시고 그 다음에 실행하면서 >> 디버깅

예를 들어 찬호님이 만드신 이 로직이요.

int go(int idx, int sum, int mx, int n, int * a) {
	if (idx == n) {
		cnt++;
		return mx;
	}
	
	int with_item = go(idx + 1, sum + a[idx], max(mx, sum % 11), n, a);
	int without_item = go(idx + 1, sum, mx, n, a);
	
	return max(with_item, without_item);
}

여기서 이런식으로 디버깅 놓으면서

int go(int idx, int sum, int mx, int n, int * a) {
	cout << idx << ": " << sum << "\n";
	if (idx == n) {
		cnt++;
		return mx;
	}
	
	int with_item = go(idx + 1, sum + a[idx], max(mx, sum % 11), n, a);
	int without_item = go(idx + 1, sum, mx, n, a);
	
	return max(with_item, without_item);
}

내가 손코딩한 그림과 디버깅한 코드가 출력한 부분이 일치하는지 확인하는 것이죠.

예를 들어 내가 손코딩한 것은

f(1, 1)

f(1, 2)

f(1, 3)

인데 디버깅하니까.

f(1, 1)

f(1, 3)

f(1, 2)

이런식의 순서로 호출되었다더라..

하면 왜 내 생각이 틀렸지 하면서 다듬고 보시면서 학습해주시면 될 거 같습니다.

이게 어느정도 되시면 문제 푸시면서 감잡으시면 될 것 같아요.

그리고 전역변수 말씀이신데요.

#include<bits/stdc++.h>
using namespace std; 
int n, temp, ret;
vector<int> v;   
const int mod = 11;
int cnt = 0;
void go(int idx, int sum){
	if(ret == 10) return;
	if(idx == n){
		ret = max(ret, sum % mod); 
		cnt++;
		return;
	}
	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";
	return 0; 
}

이 코드에서 ret을 지역변수로 하고 싶으시다는 것인데

그렇게 하시면 안됩니다.

글로벌한 해. 즉, 이 문제에서 풀이하고자 하는 해는 전역적으로 선언해서 수정 -> 해를 구한 후 -> 출력하셔야 합니다.

sum같은 경우는 이 함수를 통해서 만들어내는 sum을 만들어야 하므로. 당연히 지역변수로 선언해야 하구요.

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

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

감사합니다.

강사 큰돌 올림.