📌 문제 : 피보나치 수 5

[10870] 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

⬇️ 입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

⬆️ 출력

첫째 줄에 n번째 피보나치 수를 출력한다.

💡 코드 : 피보나치 수 5

✅ 메서드 fibonacci(int)는 기본적으로 n을 입력받아 앞 두 숫자의 합을 구해야하는데, 이를 재귀함수를 사용하여 간단하게 구현할 수 있다 : fibonacci(n-1) + fibonacci(n-2)

재귀함수를 호출하는 방식으로 계속 이전 요소들을 구하다가, n이 0, 1이 되면 0번째, 1번째 요소 0, 1을 반환하여 이후 요소들의 값을 차례대로 구할 수 있게 된다.

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		bw.write(fibonacci(n) + "");
		
		br.close();
		bw.close();
	}
	
	static int fibonacci(int n) {
		if(n == 0) return 0;
		else if(n == 1) return 1;
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

---

📌 문제 : 재귀의 귀재

[25501] 재귀의 귀재

정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다.

팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다.

어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다.

#include <stdio.h>
#include <string.h>

int recursion(const char *s, int l, int r){
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(const char *s){
    return recursion(s, 0, strlen(s)-1);
}

int main(){
    printf("ABBA: %d\n", isPalindrome("ABBA")); // 1
    printf("ABC: %d\n", isPalindrome("ABC"));   // 0
}

정휘는 위에 작성된 isPalindrome 함수를 이용하여 어떤 문자열이 팰린드롬인지 여부를 판단하려고 한다.

구체적으로는, 문자열 $S$를 isPalindrome 함수의 인자로 전달하여 팰린드롬 여부를 반환값으로 알아낼 것이다. 더불어 판별하는 과정에서 recursion 함수를 몇 번 호출하는지 셀 것이다.

정휘를 따라 여러분도 함수의 반환값과 recursion 함수의 호출 횟수를 구해보자.

⬇️ 입력

첫째 줄에 테스트케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 1\,000$)

둘째 줄부터 $T$개의 줄에 알파벳 대문자로 구성된 문자열 $S$가 주어진다. ($1 \leq \vert S\vert \leq 1\,000$)

⬆️ 출력

각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다.

💡 코드 : 재귀의 귀재

✅ 팰린드롬인지 여부를 확인하는 메서드 isPalindrome과 recursion을 문제에서 이미 C언어로 구현놨길래 이를 Java 형식으로 살짝 수정만 했다! 수정하고 보니 문제 밑에 힌트로 파이썬, 자바로 작성된 코드도 있었음 ㅎㅎ,,

물론 저것만 수정해서는 안되고, recursion 메서드의 실행 횟수 cnt를 측정해줘야 하기 때문에, recursion 메서드를 실행할 때마다 cnt를 1씩 증가시켜준다. 한 문자열에 대해 cnt를 세야 하므로 문자열이 바뀔 때마다, 즉, main 메서드의 for문에서 반복이 돌 때마다 cnt를 0으로 초기화해줘야 한다!

import java.io.*;
public class Main {
	
	static int cnt; // recursion 실행 횟수
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		for(int i=0;i<t;i++) {
			cnt = 0;
			String s = br.readLine();
			int result = isPalindrome(s);
			sb.append(result + " ").append(cnt + "\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	static int recursion(String s, int x, int y) {
		cnt++;
		if(x >= y) return 1;
		else if(s.charAt(x) != s.charAt(y)) return 0;
		return recursion(s, x+1, y-1);
	}
	
	static int isPalindrome(String s) {
		return recursion(s, 0, s.length()-1);
	}
}