[JAVA] 알고리즘 : DFS- 피보나치 재귀(메모이제이션)

 

class Main{
    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) {
        Main T = new Main();
        int n=7;
        for(int i=1; i<=n; i++) System.out.print(T.DFS(i)+" ");
    }
}

 

 

 

메모이제이션으로 시간 복잡도를 줄인 방법 

class Main{
    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]=2;
        else return fibo[n]=DFS(n-2)+DFS(n-1);
    }
    public static void main(String[] args) {
        Main T = new Main();
        int n=7;
        fibo=new int[n+1];
        T.DFS(n);
        for(int i=1; i<=n; i++) System.out.print(fibo[i]+" ");
    }
}