[Java] baekjoon_1003 : 피보나치 함수

다이나믹 프로그래밍

피포나치 함수 : Silver3

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

처음 작성한 코드

import java.io.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  static int[] cnt = new int[2];
  
  public static void main(String[] args) throws IOException {

    int T = Integer.parseInt(br.readLine());
    
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < T; i++) {
      int N = Integer.parseInt(br.readLine());
      cnt[0] = 0;
      cnt[1] = 0;
      fibonacci(N);
      sb.append(cnt[0]).append(" ").append(cnt[1]).append("\n");
    }

    bw.write(sb.toString());
    br.close();
    bw.close();
  }
  
  public static int fibonacci(int n) {
    if (n == 0) {
      cnt[0]++;
      return 0;
    } else if (n == 1) {
      cnt[1]++;
      return 1;
    } else {
      return fibonacci(n - 1) + fibonacci(n - 2);
    }
  }
}

 

ㄴ 해당 코드를 이용하면 시간초과가 발생한다.

 

 

두 번째 작성한 코드

import java.io.*;

public class Main {
  static int[] cnt0 = new int[41];
  static int[] cnt1 = new int[41];
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());
    preFibonacci();
    
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < T; i++) {
      int N = Integer.parseInt(br.readLine());
      sb.append(cnt0[N]).append(" ").append(cnt1[N]).append("\n");
    }
    bw.write(sb.toString());
    br.close();
    bw.close();
  }
  
  public static void preFibonacci() {
    cnt0[0] = 1;
    cnt1[1] = 1;
    for (int i = 2; i <= 40; i++) {
      cnt0[i] = cnt0[i - 1] + cnt0[i - 2];
      cnt1[i] = cnt1[i - 1] + cnt1[i - 2];
    }
  }
}

 

ㄴ 재귀 함수를 사용하여 피보나치 수열을 구하면 중복 계산이 많이 발생하여 시간 초과가 발생할 수 있으므로, 이를 개선하기 위해서는 다이나믹 프로그래밍 기법을 사용하여 중복 계산을 피해야 했다.

 

다이나믹 프로그래밍

이전에 계산한 값을 저장해 두었다가 필요할 때 다시 사용하는 방식이다.

피보나치 수열의 경우에도 이전에 계산한 값을 배열에 저장해 두고 필요할 때마다 사용하여 중복 계산을 피할 수 있다.

 

문제에서는 N이 40보다 작거나 같은 자연수 또는 0이라고 명시되어 있다.

피보나치 수열의 인덱스는 0부터 시작하므로, 0번째부터 40번째까지의 피보나치 수열 값을 계산해야 한다.

배열의 인덱스는 0부터 시작하므로, 배열의 크기를 41로 설정하여 0번째부터 40번째까지의 값을 저장하도록 했다.

작성한 코드에서 preFibonacci() 메소드는 미리 계산하여 Fibonacci 수열의 결과를 저장하는 역할을 한다.

Fibonacci 수열의 특성을 이용하여 0과 1의 개수를 각각 저장하는 배열인 cnt0와 cnt1을 계산한다.

 

먼저, 초기값으로 cnt0[0]과 cnt1[1]을 각각 1로 설정한 후, 반복문을 통해 2부터 45까지의 인덱스를 순회하며 Fibonacci 수열을 계산한다.

각 인덱스 i에 대해 cnt0[i]는 이전 두 값인 cnt0[i - 1]과 cnt0[i - 2]의 합으로 설정하고,

cnt1[i]도 마찬가지로 이전 두 값인 cnt1[i - 1]과 cnt1[i - 2]의 합으로 설정한다.

 

=> 이렇게 배열의 크기를 41로 설정하여 미리 계산하여 피보나치 수열을 배열에 저장해 두면, 이전에 계산한 값을 재활용하여 중복 계산을 피할 수 있다.

또한, preFibonacci() 메소드를 호출하여 배열을 미리 계산한 후에는 나중에 Fibonacci 수열을 사용할 때 배열에서 값을 직접 조회하여 사용할 수 있어 조회가 빨라진다.