99 Club 2기 | Java | Beginner
🔄️ 509. Fibonacci Number
🏷 관련 주제 : Math Dynamic Programming Recursion Memorization
Easy
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
Constraints:
0 <= n <= 30
Accepted 1.8M | Submissions 2.5M | Acceptance Rate 71.2%
✔ Solution with Recursion1
n < 2인 경우를 먼저 계산
class Solution {
public int fib(int n) {
int answer = 0;
if (n < 2) {
answer = n;
} else {
answer = fib(n - 1) + fib(n - 2);
}
return answer;
}
}채점 결과
✔ Solution with Recursion2
n > 1인 경우를 먼저 진행, 재귀함수를 먼저 호출
class Solution {
public int fib(int n) {
int answer = 0;
if (n > 1) {
answer = fib(n - 1) + fib(n - 2);
} else {
answer = n;
}
return answer;
}
}채점 결과
앞의 코드보다 실행 시간이 조금 더 걸림(8ms → 9ms)
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
📌 오늘 만난 문제 : 매개변수로 받은 n에 대하여 n번째 피보나치수를 반환하는 int fib(int n)메서드를 구현하자.
피보나치 수 : 일반적으로 f(n)으로 나타내며 피보나치 수열이라고 하는 수열을 형성0, 1로 시작하며 각 피보나치 수는 앞의 두 수의 합으로 나타내어 진다.
f(0) = 0, f(1) = 1
f(n) = f(n - 1) + f(n - 2), for n > 1
앞의 두 수의 합으로 다음 수를 나타내는 성질을 재귀함수로 나타내어n번째 피보나치 수를 반환하는 int fib(int n) 를 구현해 보자.
1. 반환할 값을 담을 int answer을 만들자.
int answer = 0;2. f(0) = 0, f(1) = 1이므로 n이 2보다 작을 때, answer에 n을 할당하자.
if (n < 2) {
answer = n;
}n >= 2이면, n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이 n번째 피보나치 수가 된다.
3. answer에 fib(n - 1) + fib(n - 2)를 할당하자.
else {
answer = fib(n - 1) + fib(n - 2);
}fib(n) = fib(n - 1) + fib(n - 2) 이므로 fib(n - 1)과 fib(n - 2)를 호출
fib(n - 1) = fib (n - 2) + fib(n - 3) 이므로 fib(n - 2)과 fib(n - 3)를 호출
fib(n - 2) = fib(n - 3) + fib(n - 4) 이므로 fib(n - 3)과 fib(n - 4)를 호출
...
fib(4) = fib(3) + fib(2) 이므로 fib(3)과 fib(2)를 호출
fib(3) = fib(2) + fib(1) 이므로 fib(2)과 fib(1)를 호출
fib(2) = fib(1) + fib(0) 이므로 fib(1)과 fib(0)를 호출
fib(1) = 1, fib(0) = 0이므로
(fib(1) 은 1, fib(0) 는 0를 반환하므로)
fib(2) = fib(1) + fib(0) = 1 + 0 = 1
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
fib(4) = fib(3) + fib(2) = 2 + 1 = 3
...
fib(n - 2) = fib(n - 3) + fib(n - 4) = ...
fib(n - 1) = fib (n - 2) + fib(n - 3) = ...
fib(n) = fib(n - 1) + fib(n - 2) = ...
호출된 fib()메서드가 역순으로 값을 반환하면서 f(n)값을 반환받을 수 있음.
4. answer에 할당된 값을 반환하자.
return answer;💬 무엇을 새롭게 알았는지
재귀함수로 피보나치 수 구하기
