DP(Dynamic Programming) 공부

피보나치 수

재귀 할 때 많이 보던 피보나치 수
원래 풀던 대로 풀면

package BOJ.selfStudy.Bronze.Two;

import java.io.*;

//https://www.acmicpc.net/problem/2747
public class solved_2747 {
    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 n = Integer.parseInt(br.readLine());

        int result = fibonachi(n);
		
        bw.write(result);
        bw.flush();
        bw.close();
    }

    public static int fibonachi(int n){
        if(n==1 ||n ==2){
            return 1;
        }else{
            return fibonachi(n-1)+fibonachi(n-2);
        }
    }
}

시간초과가 난다.
재귀를 하며 중복 계산을 하게 되므로
시간 복잡도가 O(n^2), 매우 높아진다.

그렇기 때문에 알고리즘 분류에 써져 있는 것처럼 다이나믹 프로그래밍을 사용해야 함

DP(Dynamic programming)이란?
이전 결과를 저장하면서 최적 해를 구하는 알고리즘

피보나치 수열 문제 같은 경우
fib[0]~fib[n]의 값을 배열에 저장해 두고
값을 꺼내 쓰는 것이다..

package BOJ.selfStudy.Bronze.Two;

import java.io.*;

//https://www.acmicpc.net/problem/2747
public class solved_2747 {
    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 n = Integer.parseInt(br.readLine());

        int[] fib = new int[n+1];
        for(int i = 0; i<=n;i++){
            if(i==0){
                fib[i]=0;
            }else if( i==1 || i==2){
                fib[i]=1;
            }else{
                fib[i] = fib[i-2]+ fib[i-1];
            }
        }

        bw.write(String.valueOf(fib[n]));
        bw.flush();
        bw.close();
    }
}

이러면 n번의 반복을 하며 값을 저장하고 계산하므로
시간 복잡도가 O(n)으로 줄어든다.