[Java] 2-4 피보나치 수열

문제

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

입력
첫 줄에 총 항수 N(3<=N<=45)이 입력된다.
출력
첫 줄에 피보나치 수열을 출력합니다.
예시 입력

10

예시 출력

1 1 2 3 5 8 13 21 34 55

출처
인프런 - 자바-알고리즘-문제풀이-코테대비

내 풀이

for반복문

private static void fibonacci1(int num) {
    int first = 1;
    int second = 1;
    System.out.print(first + " " + second + " ");
    for (int i = 2; i < num; i++) {
        int next = first + second;
        first = second;
        second = next;
        System.out.print(next + " ");
    }
}

---

재귀

private static void fibonacci2(int num, int first, int second) {
    if (num == 0) return;
    System.out.print(second + " ");
    int next = first + second;
    first = second;
    second = next;
    fibonacci2(num - 1, first, second);
}

재귀이긴한데 값 재활용이 불가능

다른풀이

/* 강의 풀이 */
static int[] fibo; // fibo[n]은 피보나치수열의 n번째 값을 저장

public static void main(String[] args) {
    Main T = new Main();
      Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    fibo = new int[n + 1];
    T.DFS(n);
    for (int i = 1; i <= n; i++) System.out.print(fibo[i] + " ");
}

// 피보나치 수열의 1~n번째 항의 값을 fibo에 채워넣으면서 fibo[n]을 반환하는 함수
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;

      // 값을 fibo에 저장하면서 리턴
    else return fibo[n] = DFS(n - 2) + DFS(n - 1); 
}

재활용할 수 있는 값을 따로 저장하여 동일한 계산을 줄인다

기억할 점

Memoization

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다