[JAVA] 자바 피보나치 재귀 (메모이제이션)

피보나치

피보나치 수열이란 첫째 및 둘째 항이 1이며 그 뒤의 모든 항을 바로 앞 두 항의 합인 수열을 말한다.

 

 

 

출처 : https://shoark7.github.io/programming/algorithm/피보나치-알고리즘을-해결하는-5가지-방법.html

위 그림처럼 첫 번째, 두 번째 숫자는 1이며 세 번째 숫자 부터는 앞의 두 항을 더한 값을 가진다

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

...

 

 

 

 

구현

 가장 보편적이고 간단한 방법

public class fibonacci {
    public int DFS(int n){
        if(n==1) return 1;
        else if(n==2) return 1;
        else return DFS(n - 2) + DFS(n - 1);
    }

    public static void main(String[] args) {
        fibonacci T = new fibonacci();
        int n = 10;
        for (int i = 1; i <= n; i++) System.out.print(T.DFS(i) + " ");
    }
}

결과

기대했던 결과가 잘 출력되었다.

 

 

하지만 n의 수가 증가한다면, DFS가 계속 반복적으로 호출돼 스택 프레임에 쌓이기 때문에 계산이 굉장히 오래걸린다.

이 문제를 개선하는 두 가지 알고리즘을 알아보자.

 

 

 

 

피보나치 재귀 개선ver - (1)

public class fibonacci {
    static int[] fibo;
    public int DFS(int n){
        if(n==1) return fibo[n] = 1;
        else if(n==2) return fibo[n] = 1;
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }

    public static void main(String[] args) {
        fibonacci T = new fibonacci();
        int n = 45;
        fibo = new int[n+1];
        T.DFS(n);
        for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
    }
}

 

출처 : https://news.samsungdisplay.com/23402

fibo 배열을 사용해 해당 인덱스에 계산된 값을 넣어주고 그 배열에 담긴 값들을 출력한다.

앞의 코드보다 연산 속도는 빨라지지만 여전히 "배열에 두 항의 값을 더해 넣는 동작"은 반복하게 된다.

 

 

 

출처 : https://velog.io/@sud665/피보나치수열의-고찰

예를 들어, DFS(5)의 경우 가지를 뻗어 나가면서 아래에서 fib(0), fib(1), fib(2), fib(3)들은 여러 번 호출되는 것을 확인할 수 있다.

같은 매개변수 값을 가지는 함수가 반복적으로 호출되면 fibo 배열에 값을 담는 과정도 여러 번 수행하고, 이는 연산 속도에 영향을 미친다.

 

 

 

 

피보나치 재귀 개선ver - (2)

public class fibonacci {
    static int[] fibo;
    public int DFS(int n){
        if(fibo[n] > 0) return fibo[n];
        if(n==1) return fibo[n] = 1;
        else if(n==2) return fibo[n] = 1;
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }

    public static void main(String[] args) {
        fibonacci T = new fibonacci();
        int n = 45;
        fibo = new int[n+1];
        T.DFS(n);
        for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
    }
}

fibo 배열의 값을 확인해 계산된 값이 있다면 바로 해당 값을 리턴해주어 재연산 과정을 생략해버린다.

값이 없다면 DFS(n-2) + DFS(n-1)를 통해 값을 넣어주면 된다.

위의 두 가지 방법에 비해 결과가 굉장히 빨리 나오는 것을 확인할 수 있다 !!

 

 

 

코딩 혹은 면접장에 들어가서 이런식으로 풀이한다면 "이 친구 재귀함수를 제대로 이해했군"이라고 평가받을 수 있다.

해당 방식의 메모이제이션은 꼭 기억해두고 활용하는 멋쟁이가 되자

 

 

 

 

 

출처 : 인프런 자바 알고리즘 문제풀이 입문 : 코딩테스트 대비