[백준] 10870번 : 피보나치 수 5 - JAVA [자바]

www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

---

• 문제

 

 

재귀에 대한 이해만 있다면 매우 간단한 문제다!

물론 재귀함수를 쓰지 않고 배열로도 가능하니 한 번 같이 보자.

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이 문제의 경우에는 사실 문제설명에서 다 주었다.

 

피보나치 수 부터 설명을 하자면

첫번째 항이 0 부터 시작할 경우 첫번째 항은 0, 두번째 항은 1부터 시작하여, 다음 항은 직전 항과 직전 항의 직전 항의 합으로 이루어진 수열을 의미한다.

 

즉, 피보나치 수 𝐹_𝑛 은 다음과 같이 정의할 수 있다.

𝐹_𝑛 = 𝐹_𝑛-1 + 𝐹_𝑛-2    ( 𝑛 ∈ {2, 3, 4, … } )

 

그리고 위 점화식을 이용하여 구해본다면 다음과 같다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

 

 

 

 

그러면 알고리즘으로는 어떻게 짜야할까?

 

사실 이 점화식을 그대로 이용하면 된다.

즉, 함수로 구성해보자면 다음과 같다.

 

// N 번째 피보나치 수 구하기

int Fibonacci(int N) {
	if(N == 0) return 0;
	if(N == 1) return 1;

	return Fibonacci(N - 1) + Fibonacci(N - 2);
}

 

위 코드를 한 번 이해해보자.

일단, 피보나치 수는 첫 번째 항과, 두 번째 항은 0 과 1 로 고정이다.

(𝐹₀ = 0, 𝐹₁ = 1)

 

그렇기 때문에 N 이 0 과 1 일때 각각 0 과 1 을 return 하도록 해주는 것이다.

 

 

그러면  return Fibonacci(N - 1) + Fibonacci(N - 2); 을 이해해보자.

 

이미 점화식에서도 𝐹_𝑛 = 𝐹_𝑛-1 + 𝐹_𝑛-2 이라고 썼듯이 위 문장도 똑같은 기능이다.

다만 실제로 어떻게 작동하는지는 감이 잘 오지 않을 수도 있다.

 

N = 5 이라고 가정할 때 사진으로 본다면 아래와 같다.

 

 

위와같이 Fibonacci 함수 안에서 또 Fibonacci 함수를 호출하는 식으로 재귀를 하는 것이다.

그리고 재귀를 하다가 N = 1 이거나, N = 0 이면 더이상 함수를 호출하지 않고 return 시키면서 가장 안쪽 재귀부터 하나씩 값을 더해 return 해주는 방식이다.

 

0, 1, 1, 2, 3, 5, 8, 13, … 이였으므로 

 

𝐹₅ = 5 로 위의 결과와 일치한다.

 

 

이런식으로 재귀를 하면 된다.

 

 

 

 

 

 

 

---

• 4가지 방법을 이용하여 풀이한다.

 

먼저 가장 기본적으로 재귀를 이용한 방법을 쓸 것이다.

그리고 재귀 대신 배열을 이용한 방법도 보여주려 한다.

 

입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이다.

 

즉, 재귀를 이용하여 입력을 각각 달리해보고 배열을 이용하여 입력을 각각 달리 해볼 것이다.

 

---

• 풀이

- 방법 1 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		System.out.println(fibonacci(N));

	}

	// 피보나치 함수
	static int fibonacci(int N) {
		if (N == 0)	return 0;
		if (N == 1)	return 1;
		return fibonacci(N - 1) + fibonacci(N - 2);
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

알고리즘은 위 설명에서 한 그대로 적용했으니 별다른 설명은 안하겠다.

 

---

- 방법 2 

 

 

Scanner 대신 BufferedReader 로 입력받는 방법이다.

 

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 N = Integer.parseInt(br.readLine());

		System.out.println(fibonacci(N));

	}

	// 피보나치 함수
	static int fibonacci(int N) {
		if (N == 0)	return 0;
		if (N == 1)	return 1;
		return fibonacci(N - 1) + fibonacci(N - 2);
	}
}

 

 

 

단 BufferedReader 은 문자열을 반환하기 때문에 Integer.parseInt() 메소드를 통해 String 에서 int 형으로 변환시켜준다.

 

---

- 방법 3 

 

 

 

재귀 대신 배열을 사용하는 방법이다.

재귀 메커니즘자체가 0 또는 1 을 입력받을 때까지 재귀호출을 하고, 가장 작은 값부터 더해서 재귀를 빠져나가는 식이다.

 

이 메커니즘을 배열에 그대로 적용하면 된다.

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		int N = in.nextInt();

		int[] fibonacci = new int[N + 1];	// F(0) 부터 시작하므로 N + 1 크기 생성

		for(int i = 0; i < fibonacci.length; i++) {
			// F(0) 과 F(1) 은 각각 0 과 1 로 초기화
			if(i == 0) fibonacci[0] = 0;
			else if(i == 1) fibonacci[1] = 1;            
			else fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
		}
        
		System.out.println(fibonacci[N]);

	}
}

 

 

그리고 위 코드에서도 설명했듯이 index 0 과 1 은 각각 0 과 1 로 초기화 해주어야 한다.

그렇지 않고 fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]; 을 쓰면 아래와 같이 index 가 음수값이 되어 에러가 난다.

 

( i = 0 일 경우)

fibonacci[0] = fibonacci[-1] + fibonacci[-2];  

 

( i = 1 일 경우)

fibonacci[1] = fibonacci[0] + fibonacci[-1];

 

 

 

 

---

- 방법 4 

 

 

 

배열을 사용하면서 BufferedReader 로 입력받는 방법이다.

배열 사용 알고리즘은 방법 3 과 같다.

 

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 N = Integer.parseInt(br.readLine());

		int[] fibonacci = new int[N + 1];	// F(0) 부터 시작하므로 N + 1 크기 생성

		for(int i = 0; i < fibonacci.length; i++) {
			// F(0) 과 F(1) 은 각각 0 과 1 로 초기화
			if(i == 0) fibonacci[0] = 0;
			else if(i == 1) fibonacci[1] = 1;            
			else fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
		}
        
		System.out.println(fibonacci[N]);

	}
}

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 19774780  -  방법 4 : BufferedReader + 배열

채점 번호 : 19774770  -  방법 3 : Scanner + 배열

채점 번호 : 19774762  -  방법 2 : BufferedReader + 재귀

채점 번호 : 19774759  -  방법 1 : Scanner + 재귀

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

그리고 알고리즘 방법은 유의미하게 차이가 나지는 않은듯 하다.

 

그래도 재귀 카테고리인만큼 재귀로 풀어보는 것을 추천한다.

---

• 정리

 

 

재귀의 개념이 가장 많이 적용되는 부분은 수식적으로 점화식을 표현할 수 있다던가, 일정한 패턴을 갖을 때가 많다.

 

특히 '순회' 또는 '탐색'이라는 것을 배울 때 자주 써먹을 것이다.

필자의 기억에도 재귀를 가장 많이 썼을 때가 그래프 탐색(DFS, BFS)이나 정렬을 구현할 때였을 것이다.

 

Java 가 아닌 다른 언어들은 요즘 꼬리재귀를 통해 최적화를 해주고 있으나.. 자바는 아직까진 지원 할 생각이 없는 것 같다..

그렇기 때문에 배열이나 반복문을 사용하여 구현하는 방법도 익히는게 매우 좋다.