section7.4

피보나치 수열
1) 피보나치 수열을 출력한다 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
2) 입력은 피보나치 수열의 총 항의 수 이다 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

입력설명
첫 줄에 총 항수 N(3<=N<=45)이 입력된다

출력설명
첫 줄에 피보나치 수열을 출력합니다.

입력예제 1
10

출력예제 1
1 1 2 3 5 8 13 21 34 55

 

 

 

SOLUTION

public class Answer4 {
    public static void main(String[] args) {
        // for문으로 사용하는게 훨씬 성능이 좋다
        // 재귀는 스택 프레임 호출되기 때문에 성능이 안 좋음
        // 코테 보는 중소에서는 두 방법 모두 구현하라는 문제가 출제됨
        Answer4 T = new Answer4();
        int n = 10;
        for (int i = 1; i <= n; i++) {
            System.out.print(T.DFS(i)  + " ");
        }
    }

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

 

 

 

SOLUTIONV2

public class Answer4 {
    static int[] fibo;

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

    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 class Question4 {
    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int x : arrAnswer(10, arr)) {
            System.out.print(x + " ");
        }
    }
    
    public static int[] arrAnswer(int n, int[] arr) {
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                arr[0] = 1;
            } else if (i == 1) {
                arr[1] = 1;
            } else {
                arr[i] = arr[i-1] + arr[i-2];
            }
        }
        return arr;
    }
}

혹시 몰라서 배열로도 풀어봤다