인프런 커뮤니티 질문&답변
작성한 질문수
4-B 재귀함수 질문 있습니다
작성
·
237
0
안녕하세요 선생님.
선생님께서 제공해주신 정답 코드를 보면 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)) 처럼 적어주어 재귀를 들어가야 하는 지에 대한 어려움이 있습니다. 혹시 이럴 때는 어떠한 방식으로 공부하면 좋을까요?
답변 1
0
안녕하세요 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.