백준 17478번 [재귀함수가 뭔가요?] 해결하기(C++)

백준 17478: 재귀함수가 뭔가요? [실버5]

https://www.acmicpc.net/problem/17478

 

✍️Point1 : 종료 조건 확인하기

재귀함수는 출력 조건이 많을 수록 헷갈리기 마련이다. 이럴 땐 먼저 종료 조건부터 확인하자.

재귀함수를 호출할 때마다 "____"가 추가되는데, 이 개수는 0부터 호출마다 1씩 증가한다. 

2번 호출할거라면, 호출마다 depth를 1씩 늘려서 for문으로 출력하게 해볼까? 그렇담, 종료 조건은.,?

 

 

종료 조건은 depth를 늘리다가 n과 depth가 동일해질 때가 될 것이다.

 

종료 조건이 되면,

________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"

이 부분을 출력하고 더이상의 호출을 멈춰야 한다.

✍️Point2 : 재귀의 처리 방식 이해하기

재귀 함수는 호출을 이어나가다가, 마지막 호출의 함수가 끝까지 도달하고, 그 직전 호출 함수가 실행되고,,이런 구조이다. 좀 더 알기 쉽게 표현하자면, 다음과 같다.

jh(0) 호출
    jh(1) 호출
        jh(2) 호출  // 종료 조건 도달
        "재귀함수는 자기 자신을 호출하는 함수라네" 출력
        "라고 답변하였지." (depth=2)  // 가장 깊은 곳에서부터 반환하면서 출력
    "라고 답변하였지." (depth=1)
"라고 답변하였지." (depth=0)

 

💡해결

💡Idea : depth 변수를 두어 1씩 늘리자!

 

#include<bits/stdc++.h>
using namespace std;

int n;
int depth;

void jh(int depth){
	
	for(int i=0;i<depth;i++){
		cout<<"____";
	}
	cout<<"\"재귀함수가 뭔가요?\"\n";
	
	//종료조건 
	if(depth==n){
		for(int i=0;i<depth;i++){
			cout<<"____";
		}
		cout<<"\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
		
		for(int i=0;i<depth;i++){
			cout<<"____";
		}
		cout<<"라고 답변하였지.\n";
		return;
	}
	
	for(int i=0;i<depth;i++){
		cout<<"____";
	}
	cout<<"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
	for(int i=0;i<depth;i++){
		cout<<"____";
	}
	cout<<"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
	for(int i=0;i<depth;i++){
		cout<<"____";
	}
	cout<<"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";

	
	jh(depth+1);
    for (int i = 0; i < depth; i++) {
        cout << "____";
    }
    cout << "라고 답변하였지.\n";
}

int main(){
	cin>>n;
	cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
	jh(0);
	return 0;
}

 

재귀 호출 부분 (jh(depth+1)) 밑에 "라고 답변하였지"가 출력되는 이유는,

재귀 호출이 끝나고 나야 depth의 수만큼 "라고 답변하였지"가 나오기 때문이다.

 

 

⌛시간 복잡도

주요 코드의 시간복잡도는 다음과 같이 볼 수 있다.

 

void jh(int depth) {
    // 질문 출력 (O(depth))
    for (int i = 0; i < depth; i++) { cout << "____"; }
    cout << "\"재귀함수가 뭔가요?\"\n";

    // 종료 조건
    if (depth == n) {
        for (int i = 0; i < depth; i++) { cout << "____"; }
        cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";

        for (int i = 0; i < depth; i++) { cout << "____"; }
        cout << "라고 답변하였지.\n";
        return;
    }

    // 이야기 출력 (O(depth))
    for (int i = 0; i < depth; i++) { cout << "____"; }
    cout << "대화 내용...\n";

    // 재귀 호출 (한 번)
    jh(depth + 1);

    // 답변 출력 (O(depth))
    for (int i = 0; i < depth; i++) { cout << "____"; }
    cout << "라고 답변하였지.\n";
}

 

 

시간 복잡도에 가장 큰 영향을 주는 부분은 아무래도 재귀 호출이 되는 부분일 것이다.

 

재귀 호출은 n=k일 경우 k,k-1,k-2...2,1,0 순으로 호출될 것이기 때문에, 이를 모두 더하면

O(n^2)이 된다.

 

성공!!