개발하는 호랑이

반가워욤 :)

2 분 소요

문제

백준 10870번 피보나치수 5 문제

문제 풀이

피보나치 수

피보나치 수 \(F_n\)는 다음과 같은 초기값 및 점화식으로 정의되는 수열을 말한다.
\(F_1 = F_2 = 1\)
\(F_n = F_{n-1} + F_{n-2}\)      \((n \in \lbrace3,4,…\rbrace)\)

문제는 0번째 항부터 시작하므로 아래와 같이 정의된다.
\(F_n = 0\)
\(F_1 = 1\)
\(F_n = F_{n-1} + F_{n-2}\)      \((n \in \lbrace2,3,4,…\rbrace)\)

위의 점화식을 이용해 피보나치 수를 구하면 아래와 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …

만약 n이 17이라면 n번째 피보나치 수는 1597이 된다.

재귀함수

문제는 재귀함수를 이용해서 풀면된다.
재귀함수는 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수를 말한다.

public class Main {
	public static void main(String[] args) throws IOException {
		System.out.println(Recursion(10)); // 팩토리얼 재귀함수
	}

	public static int Recursion(int number) {
		if(number <= 1) return 1; // 재귀함수 종료조건
		return number * Recursion(number - 1);
	}
}

위는 팩토리얼을 구현한 재귀함수이다. 이런식으로 함수 내부에서 자기자신을 호출하는 함수를 재귀함수라고 한다.
반복문과 마찬가지로 종료지점을 제대로 생각하지 않고 구현을하면 StackOverFlow가 발생할 수 있으니 주의해서 구현해야한다.

1.

문제를 해결하기 위한 재귀함수를 만들어 보자.

public static int fibonacci(int number) {
	if(number == 0) return 0;
	if(number == 1) return 1;

	return fibonacci(number - 2) + fibonacci(number - 1);
}

\(F_n = 0\)
\(F_1 = 1\)
\(F_n = F_{n-1} + F_{n-2}\)      \((n \in \lbrace2,3,4,…\rbrace)\)
아까 위에서 언급했듯이, 피보나치 수의 0번째 항과 1번째 항은 0과 1로 고정이다.
그것을 이용해서 number가 0 또는 1일 때 각각 0과 1을 return 해주며 재귀가 종료되도록 만들었다.

만약 number가 5라면 아래처럼 진행될 것이다.

	fibonacci(5) = fibonacci(3) + fibonacci(4); // 2 + 3 = 5
	fibonacci(4) = fibonacci(2) + fibonacci(3); // 1 + 2 = 3
	fibonacci(3) = fibonacci(1) + fibonacci(2); // 1 + 1 = 2
	fibonacci(2) = fibonacci(0) + fibonacci(1); // 0 + 1 = 1
	fibonacci(1) = 1; // 1은 1을 리턴
	fibonacci(0) = 0; // 0은 0을 리턴
  • fibonacci(5)는 fibonacci(3) + fibonacci(4)를 실행시킴
  • fibonacci(4)는 fibonacci(2) + fibonacci(3)을 실행시킴
  • 그렇게 계속 재귀를 통해 실행하다보면 fibonacci(0) 또는 fibonacci(1)을 실행시켜 각각 0과 1을 리턴시킴
  • 역방향으로 return 해주며 결국 fibonacci(5)는 5를 리턴

말로 어렵다면 아래의 그림을 참고하자.

2.

결과적으로 아래처럼 작성하면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		int fi = fibonacci(T);
		System.out.println(fi);
	}

	public static int fibonacci(int number) {
		if(number == 0) return 0;
		if(number == 1) return 1;

		return fibonacci(number - 2) + fibonacci(number - 1);
	}
}

참고하며 공부한 블로그

참고