1. 오늘의 문제

Fibonacci Number

• 출처 : leetcode

2. 문제 분석

• 피보나치 수열
• F(o) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2), for (n > 1)
• n : 정수형 변수
• 0 $\leq$ n $\leq$ 30

• 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 2
  • Input: n = 4
  • Output: 3
  • Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

3. 문제 풀이

1. 재귀 호출을 이용하면 됨
2. Base Case
   • n = 0일때, return 0
   • n < 3 일때 return 1 (어짜피 n = 2도 1을 리턴해야하기에 걍 n = 1이랑 같이 묶어줌)
3. else 구문으로 Rerruence Case 만들어줌
   • return fib(n - 1) + fib(n - 2)

4. 구현 코드

class Solution {
    public int fib(int n) {
        // 재귀 호출을 이용하면 됨
        
        // Base Case
        // n = 0일때, return 0
        if (n == 0) {
            return 0;
        // n < 3 일때 return 1 (어짜피 n = 2도 1을 리턴해야하기에 걍 n = 1이랑 같이 묶어줌)
        } else if (n < 3) {
            return 1;
        // else 구문으로 Rerruence Case 만들어줌
        // return fib(n - 1) + fib(n - 2)
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }
}

• 위의 방법은 계산 과정에서 중복을 피할 수 없지만 밑의 방법은 중복을 피할 수 있어 더욱 빠름

class Solution {
	// 재귀 함수 밖에 저장됨
    // 피보나치 수를 저장하는 데 사용됨
    int fibseq[] = new int[31];
    public int fib(int n) {
    	// n이 0이나 1일 경우 n을 그대로 반환
        if (n <= 1) return n;
        
        // fibseq[n]의 값이 있고, n이 0보다 크면
        // 즉, 이미 계산된 값이 배열에 저장되어 있으면 fibseq[n] 반환
        // 이 과정에서 중복 피함
        if (fibseq[n] != 0 && n > 0) return fibseq[n];
        
        // fibseq[n]에 값이 저장되어 있지 않다면 새로 계산한 후 return
        fibseq[n] = fib(n-1) + fib(n-2);
        return fibseq[n];
    }
}

5. 오늘의 회고

• 그냥 단순하게 생각해서 풀었지만, 동적으로 프로그래밍하면 중복을 제거해 빠르게 문제를 풀 수 있다는 것을 알게 되었다. 피보나치를 아무생각없이 풀었는데 중복을 제거할 수 있는 방법 또한 생각했어야 한다는 것을 느끼며 아직도 멀었구나 하는 생각을 하게 되었다.
• 그래도 이번에 배운 것이 도움을 줄 것이다.
  

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL