피보나치

01 May 2023 in Algorithm on Java, Coding, Test

문제

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

입력

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

출력

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

입력예제

10

출력예제

1 1 2 3 5 8 13 21 34 55

해결방법

• 메모이제이션 : 순간순간 기록하는 것.
• 재귀 함수는 함수 호출 시 마다 스택프레임이 생성되기 때문에 단일 함수 내 반복문으로 수행하는 것보다는 성능(속도)이 떨어진다.

코드

• 작은 수 부터 순서대로 호출하여 구하기

import java.util.*;

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

• 큰 수 부터 역순으로 호출하여 구하기

import java.util.*;

class Main {
    static int[] fibo;

    public int DFS(int n) {
        // n 번째 값이 존재 한다면 그 값을 리턴한다.
        if (fibo[n] > 0) return fibo[n];
        // n 이 1이라면 1을 리턴한다. 피보나치 수열은 앞의 2개가 있어야 계산할 수 있다.
        if (n == 1) return fibo[n] = 1;
        // n 이 2라면 1을 리턴한다. 피보나치 수열은 앞의 2개가 있어야 계산할 수 있다.
        else if (n == 2) return fibo[n] = 1;
        // 그 외의 경우에 n 번째 배열의 값은 n - 2 번째와 n - 1 번째 값이다.
        // 단, 최대 수 부터 역순으로 찾기 떄문에 .. 빼는 것으로 구한다.
        else return fibo[n] = DFS(n - 2) + DFS(n - 1);
    }

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