https://www.acmicpc.net/problem/10870
10870번: 피보나치 수 5
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
우선 피보나치란 수는 0과 1로 시작하여 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로 수식은 Fn = Fn-1 + Fn-2 (n ≥ 2)이다.
이 수열은 for문 또는 재귀함수로 푸는 2가지 방법이 있다.
Answer 1
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) {
int n = 0;
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
n = Integer.parseInt(br.readLine());
} catch (IOException e) {
System.err.println("ERORR = " + e.getMessage());
}
int temp1 = 0;
int temp2 = 1;
int currentNum = 0;
for (int i = 0; i < n; i++) {
temp1 = temp2;
temp2 = currentNum;
currentNum = temp1 + temp2;
}
System.out.println(currentNum);
}
}
Code Review 1
피보나치 수열을 반복문으로 풀었다.
int n = 0;
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
n = Integer.parseInt(br.readLine());
} catch (IOException e) {
System.err.println("ERORR = " + e.getMessage());
}피보나치 수열을 몇 번째까지 계산할지 `n` 변수를 선언한다.
`try-with-resources`로 try에 객체의 자원을 받아서 try문이 끝나면 그 자원을 자동으로 반환한다.
`System.in`으로 사용자로부터 입력받은 데이터를 바이트 기반 스트림으로 받는다.
`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.
`BufferedReader` 클래스로 문자 스트림을 읽는다.
`br.readLine()`으로 읽은 문자열을 `Integer.parseInt()` 메서드를 이용하여 정수로 변환하고 `n`에 대입한다.
int temp1 = 0;
int temp2 = 1;
int currentNum = 0;
for (int i = 0; i < n; i++) {
temp1 = temp2;
temp2 = currentNum;
currentNum = temp1 + temp2;
}피보나치 수열을 구하기 위해 두 개의 임시 숫자 `temp1`, `temp2`와 두 임시 숫자를 더할 현재 숫자 `currentNum`을 선언한다.
for문으로 입력받은 n번째까지 아래 로직을 반복한다.
여기서 `temp1`은 첫 번째이니 0, `temp2`는 두 번째이니 1, `currentNum`은 0으로 초기화해 준다.
예를 들어, n이 5일 때
| n | temp1 | temp2 | currentNum | result |
| 0 (for문 집입X) | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 + 0 = 1 | 1 |
| 2 | 0 | 1 | 0 + 1 = 1 | 1 |
| 3 | 1 | 1 | 1 + 1 = 2 | 2 |
| 4 | 1 | 2 | 1 + 2 = 3 | 3 |
| 5 | 2 | 3 | 2 + 3 = 5 | 5 |
위 표처럼 결과가 나온다.
Answer 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) {
int n = 0;
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
n = Integer.parseInt(br.readLine());
} catch (IOException e) {
System.err.println("ERORR = " + e.getMessage());
}
System.out.println(fibonacci(n));
}
static int fibonacci(int n) {
if (n < 2) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
Code Review 2
피보나치 수열을 재귀함수로 풀었다.
Code Review 1과 다른 코드를 설명한다.
static int fibonacci(int n) {
if (n < 2) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}지문에서도 나온 피보나치 수열의 수식은 Fn = Fn-1 + Fn-2 (n ≥ 2)이다.
따라서 이 식에 맞춰 몇 번째 피보나치 수인지를 나타내는 입력값 `n`을 파라미터로 받는 `fibonacci()` 메서드를 만든다.
`n`이 2보다 작을 때. 즉, 0 또는 1일 때 피보나치 수는 각각의 `n`과 같으므로 `n`을 반환한다.
`n`이 2부터는 재귀함수로 처리하며, Fn-1 + Fn-2 수식을 적용하여 반환한다.
예를 들어 `n`이 5일 때
| n | fibonacci(n - 1) | fibonacci(n - 2) | result |
| 5 | fibonacci(5 - 1) = fibonacci(4) = fibonacci(3) + fibonacci(2) = fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0) = fibonacci(1) + fibonacci(0) + 1 + 1 + 0 = 1 + 0 + 1 + 1 + 0 = 3 |
fibonacci(5 - 2) = fibonacci(3) = fibonacci(2) + fibonacci(1) = fibonacci(1) + fibonacci(0) + 1 = 1 + 0 + 1 = 2 |
3 + 2 = 5 |
위 표처럼 결과가 나온다.
Result
이 문제에서 결과만 봤을 때 피보나치 수열을 푸는 방법을 for문으로 하나, 재귀함수로 하나 성능에 큰 차이가 없다.
수식에 더 직관적인 재귀함수로 계산하는 것이 좋아 보이지만
n번째까지 계산하는 피보나치 수열에서 n의 값이 커질수록 for문으로 계산하는 것이 성능에 좋을 것 같다.
이유는 중복 계산이 발생하기 때문인데 Code Review 1, 2를 비교하면 알 수 있다.
for문은 현재 n번째의 결과를 가지고 다음 n번째를 구하는 수에 대입하여 재사용한다.
반면에 재귀함수는 같은 인자를 갖는 메서드가 반복된다.
따라서 n의 값이 커질수록 재귀함수를 사용하면 중복된 계산이 많아진다.
