99클럽 코테 스터디 21일차 TIL , 피보나치 수

문제

풀이

입력으로 들어오는 n번째 피보나치 수를 출력하면 됨.

제출 1 - 오답

class Solution {
    public int solution(int n) {
        int answer = 0;
        answer = fibo(n) % 1234567;
        
        return answer;
    }
    
    public int fibo(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        return fibo(n-1) + fibo(n-2);
    }
}

 

시간초과가 날 것이라고 알고 있었지만 재귀를 사용해서 기본적인 피보나치수열을 출력하도록 했다.

제출 2 - 오답

class Solution {
    public int solution(int n) {
        int[] memo = new int[100_000];
        int answer = 0;

        memo[0] = 0;
        memo[1] = 1;
        for(int i=2;i<100_000;i++){
            memo[i] = (memo[i-1] + memo[i-2])%1234567;
        }
        answer = memo[n];

        return answer;
    }
}

 

메모제이션을 사용해서 풀이했다.

테스트케이스 13번만 실패했는데 런타임 에러였다.

100,000가 들어올 수도 있기 때문에 인덱스를 늘려주어야 한다.

제출 3 - 정답

class Solution {
    public int solution(int n) {
        int[] memo = new int[100_001];
        int answer = 0;

        memo[0] = 0;
        memo[1] = 1;
        for(int i=2;i<100_001;i++){
            memo[i] = (memo[i-1] + memo[i-2])%1234567;
        }
        answer = memo[n];

        return answer;
    }
}

 

TIL

• 동적계획법
• 탑다운,  바텀 업