#피보나치 재귀(메모이제이션)

피보나치 수열을 출력하시오.

입력은 피보나치 수열의 총 항의 수이다.

만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

왼쪽부터 뻗어나가서 차례로 중복인 값들은 뻗어나가지 않는다.

1 2에서 4로간 뒤 6으로 감.

1 1 2 3 5 8 13 을 출력해야한다.

 

1.fibo 배열없이 만들게 되면 DFS 메서드를 n만큼 10번 호출해야함.

2.fibo 배열을 만들게되면 DFS(10) 하나만 호출해도 fibo배열에 값이 모두 담기므로 한번 호출하고 배열 출력

3.이미 구한 값들을 다시 구하지 않게 하면 시간복잡도가 매우 좋아짐 fibo[n] > 0일 때 해당 값만 리턴

 

1.변수 이용

public class Main {
    public static void main(String[] args) {
        int n = 30;
        int prevPrevNum = 1;
    	int prevNum = 1;
        for(int i = 3; i <= n; i++) {
            int curNum = prevPrevNum + prevNum;
            System.out.print(curNum + " ");
            prevPrevNum = prevNum;
            prevNum = curNum;
        }
    }
}

 

2.배열 이용

public class Main {
    public static void main(String[] args) {
        int n = 30;
        int[] fibo = new int[n+1];
        fibo[1] = 1;
        fibo[2] = 1;
        for(int i = 3; i <= n; i++) {
            fibo[i] = fibo[i-2] + fibo[i-1];
            System.out.print(fibo[i] + " ");
        }

    }
}

 

https://www.youtube.com/watch?v=VcCkPrGaKrs 

 

1.재귀 개선 전 / n번의 함수호출 O(2^n)

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

 

2.값을 담는 fibo[] 만들어서 재귀 개선 / 함수는 한번만 호출 O(2^n)

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

 

3.값을 구했으면 그 값을 바로 리턴

구한값은 다시 구하지 않도록 한번 더 재귀 개선 / 함수는 한번만 호출 O(n)

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