4-B 재귀함수 질문 있습니다

안녕하세요 선생님.

선생님께서 제공해주신 정답 코드를 보면 go 재귀 함수를 사용하는데 go의 재귀 부분을 이해하지 못하고 있습니다.

void go(int here){

if(here == n + 1){

int sum = 0;

for(int i = 1; i <= (1 << (n - 1)); i *= 2){

int cnt = 0;

for(int j = 1; j <= n; j++) if(a[j] & i)cnt++;

sum += min(cnt, n - cnt);

}

ret = min(ret, sum);

return;

}

{(A) 위치}

go(here + 1);

a[here] = ~a[here];

go(here + 1);

}

위 함수에서 go(1)에서 시작하고 나면 go(2) => go(3) =>
go(4) 까지 가고 나서 재귀가 한번 끝나고 난 뒤 다음의 동작이 이해가 가지 않습니다. 동작을 확인해보려고 기저 사례 코드와 go(here+1) 코드 사이({A 위치}라고 하겠습니다!)에 a[i]의 요소를 확인해보는 코드를 삽입하여 확인하였습니다.(우선 저 위치에서 a[i]를 확인하는 지도 확실하지 않습니다.) 그런데 3x3 짜리 예시입력에 대해서 행의 뒤집기에 따른 행렬 a[i]의 경우의 수가 8개가 나와야 한다고 생각되는데 A위치에서는 8가지 나오지도 않았습니다. 혹시 마지막 3줄에 따른 재귀함수가 어떻게 돌아가는 지 알 수 있을까요?

4-B 문제와는 별개로 3주차 완전탐색 부터 재귀함수에 따른 문제 풀이 방식이 대부분인데 제가 재귀 함수에 대한 이해가 조금 부족한 것 같아서 어려움을 겪고 있습니다. 재귀 함수 부분을 만들 때(예를 들어 void go(int y, int x){~~} 라면) 언제 다시 (예를 들어 go(ny,nx)) 처럼 적어주어 재귀를 들어가야 하는 지에 대한 어려움이 있습니다. 혹시 이럴 때는 어떠한 방식으로 공부하면 좋을까요?

안녕하세요 1212님 ㅎㅎ

위 함수에서 go(1)에서 시작하고 나면 go(2) => go(3) =>
go(4) 까지 가고 나서 재귀가 한번 끝나고 난 뒤 다음의 동작이 이해가 가지 않습니다.

재귀가 끝난후.

go(4) -> 뒤집고 -> go(4) ...

가 작동이 됩니다.

이거는 함수호출에 따라 트리를 그려보면 쉽습니다.

제가 한번 그려봤는데요.

이렇게 됩니다.

디버깅 코드 - 출력되는 것과 비교해서 볼까요?

#include<bits/stdc++.h>
#define maxn 200005
typedef long long ll;
using namespace std;   
const int INF = 987654321;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1}; 
int n, a[44], ret = INF;
string s; 
void go(int here){
    cout << here << "\n";
	if(here == n + 1){
		int sum = 0; 
		for(int i = 1; i <= (1 << (n - 1)); i *= 2){
			int cnt = 0; 
			for(int j = 1; j <= n; j++) if(a[j] & i)cnt++;
			sum += min(cnt, n - cnt); 
		}
		ret = min(ret, sum);
		return;
	} 
	go(here + 1);
    cout << "뒤집기얍!" << "\n";
	a[here] = ~a[here];
	go(here + 1);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n; 
	for(int i = 1; i <= n; i++){
		cin >> s; 
		int value = 1; 
		for(int j = 0; j < s.size(); j++){
			if(s[j] == 'T')a[i] |= value; 
			value *= 2;
		}
	}   
	go(1);
	cout << ret << "\n";
    return 0;
}

출력

1
2
3
4
뒤집기얍!
4
뒤집기얍!
3
4
뒤집기얍!
4
뒤집기얍!
2
3
4
뒤집기얍!
4
뒤집기얍!
3
4
뒤집기얍!
4
2

제가 그린 화살표와 디버깅 출력이 똑같은 것이 보이시나요?

이렇게 공부하시면 됩니다.

재귀 함수 부분을 만들 때(예를 들어 void go(int y, int x){~~} 라면) 언제 다시 (예를 들어 go(ny,nx)) 처럼 적어주어 재귀를 들어가야 하는 지에 대한 어려움이 있습니다. 혹시 이럴 때는 어떠한 방식으로 공부하면 좋을까요?

이렇게 생각하시면 됩니다.

어떤 경우의 수가 있는가. 원복을 해야 하는가.

를 중점으로 틀 안에서 로직을 구현해보자.

예를 들어 3가지의 경우의 수가 있다면.

go -> go, go, go 이렇게 되겠죠?

형식은

go(){

    for(int i = 0; i < 3; i++) go(i)

}

이런꼴이 될 겁니다.

다만 여기서 원복이 필요한 경우

즉, a -> b 로 갔다가 다시 a -> c 이런것을 구현할 때 b까지 가서 상태값이 변화된 상태로 로직을 수행하는 것이 아닌 a라는 상태값으로 온전히 변화시킨다음에 해야 한다면.

go(){
    for(int i = 0; i < 3; i++) {
        visited[i] = 1; 
        go(i);
        visited[i] = 0;
    }
}

이런 꼴의 로직이 추가가 될 것입니다.

그리고 재귀함수는 무조건 기저사례가 있어야 한다고 말씀을 드렸죠?

그래서 최종 꼴은.

go(){
    if(){
        return;
    }
    // main logic
    for(int i = 0; i < 3; i++) {
        visited[i] = 1; 
        go(i);
        visited[i] = 0;
    }
}

앞의 코드와 같이 될 것입니다.

이렇게

기저, 메인 로직, 함수호출

이러한 틀이 있고 이 틀을 기반으로 로직을 구축하는 것이다 라고 하면서 공부하시면 됩니다.

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

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

감사합니다.

강사 큰돌 올림.

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