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

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

 

문제를 보고 가장 먼저 생각난 것은 재귀함수를 사용하는 것이었다.

 

첫번째 코드

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

 

하지만 7번 부터 오류가 났다.

자료형도 조건에 맞게 사용한거 같은데

도저히 모르겠어서 인터넷 검색을 하였다.

 

 

그러다

를 보게 되었다.

 

예전에 배웠던 기억이 있어 적용하였지만

 

2번째 코드

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

 

하지만 이렇게 하여도 똑같이 오류가 계속 났다.

 

그러다 재귀함수를 사용하면 시간복잡도가 O(n²)가 되는것을 알게되었다.

따라서 배열을 사용하여 결과를 저장하여 처리하여 시간을 맞추었다.

 

최종코드

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n+1];
        
        for(int i=0;i<=n;i++){
            if(i<2){
                fibo[i]=i;
            }else{
                fibo[i]= (fibo[i-1]+fibo[i-2])%1234567;
            }
        }
        return fibo[n];  
    }
}

 

해결은 되지 않았지만

모듈러 연산을 공부해야겠다는 것과 재귀의 시간 복잡도를 공부해야겠다고 생각하게 되엇다.