99클럽 코테 스터디 15일차 TIL + DP

백준

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

1003번: 피보나치 함수

---

- 오늘의 학습 키워드 : DP

- 공부한 내용 본인의 언어로 정리하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  static int[][] call;
  static int[] topDown_memo;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int T = Integer.parseInt(br.readLine());

    for (int i=0; i<T; i++) {
      int N = Integer.parseInt(br.readLine());
      topDown_memo = new int[N+1];
      call = new int[N+2][2];

      fibonacci(N);
      sb.append(call[N][0]).append(" ").append(call[N][1]).append("\n");
    }
    System.out.println(sb);
  }

  public static int fibonacci(int N) {
    // 기저 상태 도달 시, 값 초기화 및 호출 횟수 저장
    if (N == 0) {
      call[0][0] = 1; // 0 값은 1개
      call[0][1] = 0; // 1 값은 0개
      return topDown_memo[0] = 0;
    }
    else if (N == 1) {
      call[1][0] = 0; // 0 값은 0개
      call[1][1] = 1; // 1 값은 1개
      return topDown_memo[1] = 1;
    }

    // 저장된 값이 있는 경우 그대로 사용
    if (topDown_memo[N] > 0) {
      return topDown_memo[N];
    }
    // 재귀 함수로 값 저장
    topDown_memo[N] = fibonacci(N-1) + fibonacci(N-2);
    call[N][0] = call[N-1][0] + call[N-2][0];
    call[N][1] = call[N-1][1] + call[N-2][1];
    return topDown_memo[N];
  }
}

- 오늘의 회고 : 피보나치 수열의 값을 구할 때, 재귀 함수로 다 돌리는 방법도 있지만, 비슷한 값을 반복해서 사용할 경우에 값을 저장하는 DP 방법을 사용해서 O(N^2) -> O(N)으로 시간 복잡도를 줄일 수 있다.

0과 1의 호출 값을 찾으려고 할 때는 [N][0] 호출 값이 [N-1][0] + [N-2][0] 호출 값을 더한다는 패턴을 파악함으로써 문제를 해결할 수 있었다.

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중