DFS 피보나치 수열 (메모제이션)

Array로 푼 피보나치수열

: Array로 푼것이 재귀함수보다 더 성능이 좋다.

public class Fibonacci {

    private int[] solution(int n) {

        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;

        for (int i = 2; i < n; i++) { //10 -> 2~9
            arr[i] = arr[i-2] + arr[i-1];
        }
        return arr;
    }

    public static void main(String[] args) {

        Fibonacci main = new Fibonacci();

        Scanner si = new Scanner(System.in);
        int N = si.nextInt();

        for(int x : main.solution(N))
            System.out.print(x+" ");
    }
}

재귀함수(DFS)로 푼 피보나치수열

public class FibonacciDFS {
    public int DFS(int n) {
        // 종료 조건
        if (n==1 || n==2) return 1;
        else {
            return DFS(n-1)+DFS(n-2);
        }
    }

    public static void main(String[] args) {
        FibonacciDFS T = new FibonacciDFS();

        for(int i=1; i<=n; i++){    // 1부터 시작
            System.out.print(T.DFS(i)+" ");
        }
    }
}

개선된 피보나치 수열

: 메모제이션을 이용, 배열에 저장하고 이미 계산된 것은 재사용해서 처리속도가 높아진다!

// 4. 피보나치(DFS) -> 배열보다 성능이 안좋아 재귀호출은 상당한 메모리 잡아먹어
public class FibonacciDFS {
    static int[] fibo;		// class 밑에 전역변수로 배열 생성
    public int DFS(int n) {
        if(fibo[n] > 0) return fibo[n];     // 메모제이션 key : 이코드 없고 있고의 성능차이가 확실함! 왼쪽 트리 값을 미리 기록해서 return
        if(n == 1) return fibo[n]=1;
        else if(n == 2) return fibo[n]=2;
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }

    public static void main(String[] args) {
        FibonacciDFS T = new FibonacciDFS();
        int n = 45;     // 45면 엄청 버퍼링 -> 메모제이션 필요! static int[] fibo;
        fibo = new int[n + 1];   // 1부터 시작
        T.DFS(n);
        for(int i=1; i<=n; i++){    // 1부터 시작
//            System.out.print(T.DFS(i) + " ");
            System.out.print(fibo[i] + " ");
        }

    }

}