99클럽 코테 스터디 14일차 TIL Fibonacci Number

Fibonacci Number

• 문제 풀이

  1. n이 2보다 작을때는 단순히 주어진 n을 리턴하면 된다.
  2. 그외에는 F(n) = F(n-1) + F(n - 2)에 대해선 재귀함수를 돌려 문제를 해결했다.

• 풀이 소스

class Solution {
    public int fib(int n) {
        if(n<2){
            return n;
        }
        return fib(n-1) + fib(n-2);
    }
}

• 풀이 소스 메모이제이션 사용

class Solution {
    static long[] memo;
    public int fib(int n) {
        memo = new long[n+1];
        return Long.valueOf(recursive(n)).intValue();
    }

    public long recursive(int n){
        if(n<2){
            return n;
        }
        if(memo[n] == 0){
            memo[n] = recursive(n-1) + recursive(n-2);
        }
        return memo[n];
    }
}

• 오늘의 회고

  • 문제 시도 및 해결

    • 이번 문제는 문제설명에서 답을 줬다고 생각한다. 공식을 다 알려주었기 때문이다.
    • 조건에 맞게 재귀함수를 풀면되는 문제였다.

• 학습 내용 및 회고

  • 처음에 문제를 받자마자 피보나치수열에 대해서 잘 알지 못해서 공식을 안줬다면 풀기 어려웟을 거 같다.
  • 특정 패턴을 찾는 문제인 줄 알았다.
  • 피보나치수열에 대해 검색해보았는데 위 코드로 문제를 해결하면 복잡도가 O(n^2)이라고 하여 메모이제이션을 사용하는 코드를 추천하길래 그 방식으로도 해결해보았다.

• 다음 배울것

  • Spring boot 로그인, session, cookie 공부
  • 코테 문제 풀이