[Algorithm/Java] 알고리즘 자바 피보나치, 메모이제이션 (코딩테스트, Recursive, Tree, Graph, DFS, BFS, Recursion Function, 재귀 함수, Fibonacci, Memoization)

---

1. 문제 설명

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

 

2. 문제 코드 및 풀이 설명

import java.util.Scanner;

public class Fibonacci {
  static int[] fibo; // 성능 개선을 위해 함수를 한번 돌았을때 값을 저장해줄 배열, 메모이제이션

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

  // 피보나치 수열
  // 1이나 2인 경우는 1이 리턴
  // 나머지의 경우는 바로 왼쪽의 값과 왼쪽 두번째의 값을 더한 값을 리턴
  public int DFS(int n) {
    if(fibo[n] > 0) return fibo[n]; // 만약 이미 계산 해놓은 값이 있다면 더 이상 계산하지 않고 그 값을 리턴
    if (n == 1) return fibo[n] = 1; // 1이면 1리턴
    else if (n == 2) return fibo[n] = 1; // 2이면 1리턴
    else return fibo[n] = DFS(n - 2) + DFS(n - 1);
  }
}

 

3. 출력 예시

입력
12

출력
1 1 2 3 5 8 13 21 34 55 89 144

 

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의