BOJ 17478번 : 재귀함수가 뭔가요?

안녕하세요. 지난 포스팅의 BOJ 10870번 : 피보나치 수 5에서는 재귀함수를 이용해 피보나치 수열을 구하는 문제를 풀어보았습니다. 오늘은 재귀함수와 관련된 재미있는 문제를 풀어보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 재귀함수의 정의
• 전역변수 선언 : global 

 

제출 코드 1

global N

def recursive(n) :
    print('_' * (4 * (N - n)) + '"재귀함수가 뭔가요?"')
    if n == 0 : 
        print('_' * (4 * (N - n))  + '"재귀함수는 자기 자신을 호출하는 함수라네"')
    else : 
        print('_' * (4 * (N - n)) + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
        print('_' * (4 * (N - n)) + '마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
        print('_' * (4 * (N - n)) + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
        recursive(n - 1)
    print('_' * (4 * (N - n)) + '라고 답변하였지.')

N =  int(input())
print('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.')
recursive(N)

 

해설

이 문제의 핵심은 예제 출력을 잘 분석하고 어떤 부분이 반복되는 지 확인하는 것입니다. 

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.

일단, 첫번째 문자열 출력은 처음에만 나오기 때문에 함수를 호출하기 전에 한번 출력해주면 됩니다. 

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

다음에는 함수를 마지막으로 호출할 때는 위 문자열을 출력하게 됩니다. 즉, 종료조건이 되겠네요. 정수형 $N$을 입력받고 $N = 0$이면 위 문자열을 출력해주면 됩니다. 다음으로 중점적으로 신경써야할 것은 '_'입니다. 잘 보시면 처음에 함수를 호출할 때는 없고 두번째 함수 호출부터 4, 8, 12, 16과 같이 공차가 4고 초항이 0인 등차수열을 이루고 있습니다. 함수를 호출한 횟수에 따라서 '_'의 출력 개수가 증가하는 것을 볼 수 있죠. 따라서, 함수를 호출한 횟수를 저장해야하는 데 이는 입력받은 $N$에서 $n$ 값을 빼면 얻을 수 있습니다. 따라서 위 제출 코드에서 4 * (N - n)이 이 것을 의미합니다. 이때, $N$은 함수 내부에서 알 수 없기 때문에 global 키워드을 통해 함수가 언제든지 해당 값을 알 수 있게 만들어주면 됩니다. 이와 같이 선언하는 방식을 전역변수 선언이라고 합니다. 

 

제출 코드 2

global N

def recursive(n) :
    t = 4 * (N - n)
    print('_' * t + '"재귀함수가 뭔가요?"')
    if n == 0 : 
        print('_' * t  + '"재귀함수는 자기 자신을 호출하는 함수라네"')
    else : 
        print('_' * t + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
        print('_' * t + '마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
        print('_' * t + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
        recursive(n - 1)
    print('_' * t + '라고 답변하였지.')

N =  int(input())
print('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.')
recursive(N)

 

해설

기존의 코드에서 반복되는 변수인 4 * (N - n)를 공차변수 t에 대입하여 코드 길이를 보다 줄였습니다. 

 

참고자료 및 그림출처

백준 코딩 문제

 

변경사항

22.07.26 : 제출 코드 2 및 해설 추가