21.07.02 - [PG] 피보나치 수

[suhyunsim]

문제

• 피보나치 수

핵심 아이디어

• DP
  • 모든 문제를 풀어야 함
  • 모든 문제는 한 번만 풀어야 함
  • 문제의 개수 (N) * 문제 1개를 푸는 시간(1) = O(N)
• 다이나믹 프로그래밍에서 재귀로 푸는 방법 (Top-Down)

int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        if (memo[n] > 0) {
            return memo[n];
        }
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return memo[n];
    }
}

• 다이나믹 프로그래밍에서 반복문으로 푸는 방법 (Bottom-up)
• DP 문제를 푸는 방법
  1. 점화식 정의 ex. D[N] = N번 째 피보나치 수
  2. 문제를 적게 만들 수 있는 방법 찾기 ex. Fn = Fn-1 + Fn-2 (직접 찾아야 하는 경우도 있고 이 문제처럼 언급하는 경우도 있음)

어려운 점, 실수

풀이

시간초과 나는 재귀 풀이

class Solution {
    public int solution(int n) {
        return fibonacci(n) % 1234567;
    }

    private static int fibonacci(int n) {
        if (n == 0 || n == 1) return n;
        else return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

단순 반복문으로 풀이

package main.java.com.poogle.PG;

public class Solution {
    static int solution(int n) {
        int ans = 0;
        int a1 = 1;
        int a2 = 1;
        if (n == 1 || n == 2) return 1;
        else {
            for (int i = 3; i <= n; i++) {
                ans = (a1 + a2) % 1234567;
                a1 = a2;
                a2 = ans;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        System.out.println(solution(3));
        System.out.println(solution(5));
    }
}