[인프런] 07_04 피보나치 재귀(메모이제이션)

📖  문제

---

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

출력 예시

 

⚠️  주의사항

---

• 재귀함수를 이용 할 것
  • 메모이제이션 기법을 활용해 볼 것

✍️  이해

---

/**
 * 1. N 입력
 * 2. DFS에 N값 넘김
 * 3. 1이나 2일때는 1 값 리턴
 * 4. 그 외에는 N-2 + N-1 즉 N의 왼쪽 값 2개 더하기
 *  4-1. 위에 내용으로 끝내도 코드는 돌아가지만 숫자가 커질 수록 너무 많은 양의 수를 재귀
 *  4-2. N 번째 값이 이미 0보다 크다면 더 이상 볼 필요 없이 N 번째 값 리턴
 * 5. 스택프레임 구조이므로 이전에 풀었던 for문과 속도차이가 많이 남
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int[] answer;

    public int DFS(int N) {
        // 없어도 돌아가지만 속도에서 차이가 엄청나게 남
        // 이미 구한 값이 존재하면 그 값을 가져오는거 이므로 "메모이제이션"이라고 불림
        if (answer[N] > 0) return answer[N];

        if (N == 1 || N == 2) return answer[N] = 1;
        else return answer[N] = DFS(N - 2) + DFS(N - 1);
    }


    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        answer = new int[N + 1];

        T.DFS(N);

        for (int i = 1; i <= N; i++) System.out.print(answer[i]  + " ");
    }
}

 

---

2022.01.21 - [[Java] 인프런 문제풀이/Array(배열)] - [인프런] 02_04 피보나치 수열

[인프런] 02_04 피보나치 수열

 

위 문제와 똑같은 문제를 for문으로 푼 내용입니다.
하지만 속도는 for > 재귀 입니다.
그 이유는 재귀는 계속 메모리에 스택프레임이 누적되기 때문에 속도차이가 생길 수 밖에 없습니다.