알고리즘
[C++] Boj 17478 재귀함수가 뭔가요?
(ꐦ •᷄ࡇ•᷅)
2025. 1. 9. 09:54
문제 링크
접근
우선 어제 배웠던 3단계 방식을 토대로 차례대로 접근하였다.
- 함수 원형 설정
- base condition 설정
- 재귀 식 구현
1. 함수 원형 설정
출력만 하는 것이므로 void 형, 또 횟수를 받아야 할 것 같아서 매개변수를 int n으로 줬다.
void Solve(int n);
2. base condition 설정
함수가 어떤 조건에서 멈출지 생각해 보았는데, n을 1씩 증가시킬 때 n이 사용자가 입력한 수가 되면 "재귀 함수가 뭔가요?"에 대한 질문을 하고 거기서 함수를 다시 호출하지 않고 답변을 하는 것을 볼 수 있다. 따라서 n == N일 때, 답변하고 끝마무리까지 하고 return 하게끔 설정했다.
3. 재귀 식 구현
void Solve(int n)
{
// 질문
if (n == N)
{
// 대답
// 마무리
return;
}
// 어쩌구저쩌구
Sovle(n+1)
// 마무리
}
코드
#include <iostream>
using namespace std;
const string str[] =
{
"어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n",
"\"재귀함수가 뭔가요?\"\n",
"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n",
"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n",
"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n",
"\"재귀함수는 자기 자신을 호출하는 함수라네\"\n",
"라고 답변하였지.\n"
};
void Solve(int n);
string printUnderBar(int n);
int N;
void Solve(int n)
{
cout << printUnderBar(n) + str[1];
if (n == N)
{
cout << printUnderBar(n) + str[5];
cout << printUnderBar(n) + str[6];
return;
}
cout << printUnderBar(n) + str[2];
cout << printUnderBar(n) + str[3];
cout << printUnderBar(n) + str[4];
Solve(n + 1);
cout << printUnderBar(n) + str[6];
}
string printUnderBar(int n)
{
string str = "";
for (int i = 0; i < n; i++)
{
str += "____";
}
return str;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
Solve(0);
return 0;
}
결과
의문점
재귀함수는 풀면 풀수록 정답을 맞혀도 이게 진짜 맞나? 라는 의문이 든다. 아마 절차지향 사고 방식을 탈피하지 못했기 때문이라 생각한다. 다른 사람의 코드를 많이 볼 필요가 있다고 생각해 바킹독님의 해설 코드를 봤다.
코드
// Authored by : cpprhtn
// Co-authored by : -
// http://boj.kr/67c805f6167e49bebd8c13e9b0df4493
#include <bits/stdc++.h>
using namespace std;
int N;
void _bar(const char* str, int stk){
for (int j = 0; j < stk; ++j) cout << "____";
cout << str;
}
void solve(int cnt){
_bar("\"재귀함수가 뭔가요?\"\n", cnt);
if (cnt == N) _bar("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n", cnt);
else{
_bar("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n", cnt);
_bar("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n", cnt);
_bar("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n", cnt);
solve(cnt + 1);
}
_bar("라고 답변하였지.\n", cnt);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
solve(0);
}
나랑 비슷한데 조금 달랐다. 나는 재귀 함수는 무조건 return 해야 돼! 라는 생각에 사로잡혀 return을 하여 코드를 더 반복되게 만들었다. 하지만 if, else를 사용하여 재귀 호출을 하면 반복되는 코드를 조금 줄일 수 있다.
개선된 코드
#include <iostream>
using namespace std;
const string str[] =
{
"어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n",
"\"재귀함수가 뭔가요?\"\n",
"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n",
"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n",
"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n",
"\"재귀함수는 자기 자신을 호출하는 함수라네\"\n",
"라고 답변하였지.\n"
};
void Solve(int n);
string printUnderBar(int n);
int N;
void Solve(int n)
{
cout << printUnderBar(n) + str[1];
if (n == N)
{
cout << printUnderBar(n) + str[5];
}
else
{
cout << printUnderBar(n) + str[2];
cout << printUnderBar(n) + str[3];
cout << printUnderBar(n) + str[4];
Solve(n + 1);
}
cout << printUnderBar(n) + str[6];
}
string printUnderBar(int n)
{
string str = "";
for (int i = 0; i < n; i++)
{
str += "____";
}
return str;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
Solve(0);
return 0;
}
뭔가 더 깔끔해져서 찝찝했던 조금 기분이 나아졌다.