[프로그래머스] 피보나치의 수 (Java)

프로그래머스 피보나치의 수

문제풀이

피보나치의 수는 다이나믹프로그래밍을 설명하는 기초 문제일 정도로 명확하게 알고 넘어가야한다. 아주 잘 정리된 피보나치 수열을 구하는 여러가지 알고리즘 글이 있어서 이를 바탕으로 다시 공부하였다.

• 단순 재귀는 O(2^n)
• 단순 반복은 O(n)
• 다이나믹프로그래밍 재귀, 반복 O(n)

구현코드

  class Solution {
      static int mod = 1234567;
      static int[] memory = new int[100001];

    public int solution(int n) {
        int answer = 0;
        memory[1] = 1;

        answer = fibo(n);

        return answer;
    }

      public int fibo(int n){
          if(n < 2) return n;
          if(memory[n] != 0) return memory[n];

          return memory[n] = (fibo(n - 1) + fibo(n - 2)) % mod;
      }
  }