[데일리코딩] 피보나치, 메모이제이션

피보나치 수열 중 n번째 항의 수를 리턴하는 간단한 문제였다.

 

 

입력 : int n

출력 : int타입

 

💡주의사항

재귀함수로 풀어야 한다

반복문의 사용이 금지된다.

 

 

 

아 별거아니네~ 하고 처음에는 재귀를 사용해서 룰루랄라 풀어서 제출하려고 했다.

 

 근데 자꾸 시간초과가 뜨는 것이다..

 

알고보니 재귀를 이용한 문제는 메모리를 상당히 잡아먹는 비효율적인 방법이고

 

위 방법대로 푼다면

함수들의 총 호출횟수가 대략 2^n 근처라서 n이 25~30 넘어가면 힘들어진다고 한다.

 

따라서 메모이제이션을 쓰면 효율적인 알고리즘(O(N))으로 연산을 줄일 수 있다!

 

🔎메모이제이션이란

이미 계산된 값을 배열에 저장하고 필요시마다 값을 불러와 쓴다.

이렇게 하여 불필요하게 중복되는 계산을 줄이는 것이다!

 

 

 

public class fibonacci_23 {

    public static void main(String[] args) {
        int output = fibonacci(30);
        System.out.println(output);
    }

    public static int fibonacci(int num) {
        ArrayList<Integer> memo = new ArrayList<>(); //계산된 값을 담아줄 ArratList생성
        memo.add(0); //0번째 값은 항상 0임
        memo.add(1); //1번째 값은 항상 1임
        return fibo(memo, num); //함수 호출
    }

    public static int fibo(ArrayList<Integer> memo, int num) {
        if (memo.size() <= num) { //num번째 수가 계산되어 있지 않다면
            memo.add(fibo(memo,num - 1) + fibo(memo,num - 2)); //num-1값과 num-1값을 더한 값을 저장해준다.
        }
        
        //num번째 수가 계산되어 있으면 여기로 넘어올 수 있다.
        return memo.get(num); //num번째 수를 리턴
    }
}