동적 프로그래밍(Dynamic Programming)

 

 

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

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        System.out.println(fibonacci(N));

    }

피보나치 수열을 다음과 같은 로직으로 짠다면, 시간 복잡도는 2^n 이 나오게 된다. 

 

 

예를 들어 Index 6의 값을 구한다고 가정해보자. 그렇다면 전의 두 수를 알아야 하고, 다시 전의 두 수들은 다시 전의 전 두 수 들을 알아야 한다. 즉 x2씩 계속 커지는 것이다. 그런데 이 때, 3이나 4의 값들은 여러번 반복해서 구해진다. 이 때 구한 값들을 필요할 때 마다 다시 구하지 않고, 값을 저장해놓았다면 복잡도가 많이 줄어들 것이다. 

 

 static int fibonacci(int n){
        int store[] = new int[100];
        if(n==1) return 1;
       if(n==2) return 1;
       if(store[n]!=0) return store[n];
       return store[n]= fibonacci(n-1) + fibonacci(n-2);
    }

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        System.out.println(fibonacci(N));

즉 위와 같이 밑의 두 줄 부분을 추가해준다.

 if(store[n]!=0) return store[n];
  return store[n]= fibonacci(n-1) + fibonacci(n-2);

 

이렇게 하는 기법을 Memoization 이라고 한다. 이렇게 함으로서 시간 복잡도를 O(n)으로 획기적으로 줄일 수 있다.

 

 

 

동빈나 알고리즘 강의 참조

https://www.youtube.com/watch?v=FmXZG7D8nS4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=21

https://blog.naver.com/ndb796