다이나믹 프로그래밍(DP)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘은

1. 다이나믹 프로그래밍

2. 분할 정복

 

총 2가지가 있다.

 

큰 문제를 여러개의 작은 문제로 나누었을때

작은 문제가 문제끼리 중복이 가능한것이 DP이고

중복이 불가능한것이 분할정복기법이다.

 

 

그중에서 이번에는 다이나믹 프로그래밍에 대해서 공부해 보겠다.

 

 

작은 예시를 들어보겠다. 피보나치 수열이라고 많이 들어봤을것이다 

0 1 1 2 3 5 8 13 21 34 55 와 같이

n번째 수는 n-1번째 수와 n-2번째 수의 합으로 이루어져 있는 수열을 피보나치 수열이라고 한다

 

우리는 보통 피보나치 수열 풀때 

 

 

import java.util.*;
public class Main {
    public static void main(String[] args){
        System.out.println(     fibonacci(10));
    }


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

 

 

이와 같은 코드로 풀이를 한다 

 

예를 들어 피보나치 수열의 10번째 수를 구하고 싶다 하면

fibonacci(9)+fibonacci(8)를 알아야 하는데

이것은 바로 나오는게 아니다

fibonacci(9)=fibonacci(8)+fibonacci(7)이고

fibonacci(8)+fibonacci(7)+fibonacci(6)이다 

또 여기서 끝이 아니다 긴말은 생략하겠다

한마디로 연산횟수가 많이 소요된다

시간복잡도를 보면 

1개를 호출하면 2개가 되고

2개를 호출하면 4개가 되므로 

0(2^N)이 된다

 

 

 

fibonacci(9)와 fibonacci(8)의 값을 어딘가에 메모해놓고 필요할때마다 사용하면 얼마나 좋겠는가?

이렇게 문제의 답을 한번 구했으면 어딘가에 메모해놓는 Memoization기법을 사용하는 기법을 DP(다이나믹 프로그래밍)이라고 한다 

 

 

이 피보나치 수열을 DP로 풀어보자 

import java.util.*;
public class Main {
    public static  int [] memo=new int[100]; //메모할 저장소
    public static void main(String[] args){
        System.out.println(     fibonacci(10));
    }


    public static int fibonacci (int n){
        if(n<=1){
            return n;
        }
        else{
            if(memo[n]>0){  // n이라는 수의 결과값을 담고있는 memo배열의 값의 0보다 크다는것은 그 수에 대해 계산한 적이 있다는 뜻이다
                return memo[n]; // 한번 메모해놓은 수는 계산 할 필요없다
            }
            //결과값을 메모해놓은 수가 아니라면
            memo[n]=fibonacci(n-1)+fibonacci(n-2);
            return memo[n];
        }
    }
}

 

 

DP란 모든 문제를 1번씩만 풀고 그 다음에 풀때는 메모해놓은 배열에서 값을 꺼내기만 하면 되는 원리이므로

시간 복잡도는 문제의 개수 * 문제 1개를 푸는 시간(함수의 시간복잡도)가 된다 

문제의 개수가 n개라고 했을때

피보나치수열을 구하는 함수의 시간복잡도는 덧셈 1개이므로 O(1)이다 

DP로 푼 피보나치 수열의 시간복잡도는 O(N)이다 

O(2^N)과 비교했을때 어마어마하게 준 모습이다

 

 

 

다이나믹을 구현하는 방식에는 두가지가 있는데 

 

1. Top-down (재귀사용)

-> 큰 문제부터 문제를 쪼개면서 작은 문제를 만들고 다시 그 문제들을 합쳐나가면서 원래문제를 푸는 방식 

2. Bottom-up (문제를 작은걸 다풀면 그것보다 하나큰 문제는 풀수있고 또 그것보다 하나큰 문제풀수 있고 이런 방식)

->작은 문제들을 모아서 큰문제들을 만들고 다시 작은 문제들을 모아서 큰문제를 만들어서 쌓아올라가는 방식 

-> 주로 반복문을 사용해서 구현한다 

 

 

 

Top-down방식은 아까 피보나치 수열을 재귀를 사용해서 푼 예시이고 

Bottom-up방식을 구현한 코드는 

 

public class Main {
    public static  int [] dp=new int[100]; //메모할 저장소
    public static void main(String[] args){
        System.out.println(     fibonacci(10));
    }


    public static int fibonacci (int n){
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }

        return dp[n];
    }
}

 

 

이렇게 가장 작은 문제 2개 풀어두고 

반복문을 사용하여 

0과 1보다 큰 문제(2)를 풀고 

또 그다음 큰 문제(3)를 푸는 방식으로 모든 문제를 푸는 방식이다 

 

 

굳이 top-down  bottom up 둘다 할 줄 알 필요는 없다

이 중에서 자기한테 편한 방법을 사용하면 된다 (나는 개인적으로 bottom up이 편해 보인다)

 

top-down과 bottom-up과 시간차이는 알 수 없다 

딱봤을때는 재귀를 사용하면 stack을 사용하기 때문에 stackoverflow를 발생시킬수도 있으니

반복문이 빨라 보이지만 사실 알 수 없다 그리고 그렇게 둘의 시간차이를 고려하지 않아도 된다.

 

 

다이나믹 문제 풀이 전략

 

1. 문제에서 구하려고 하는 답을 문자으로 나타낸다

2. ex) 피보나치 수를 구하는 문제 

   ex)  N번째 피보나치 수 

4. 이제 그 문장에 나와 있는 변수의 개수만큼 메모하는 배열을 만든다 

5. top-down인 경우에는 재귀 호출의 인자의 개수만큼 배열을 만든다  

6. 문제를 작은 문제로 나누고 수식을 이용해서 문제를 표현해야 한다 

 

쉽게 말하면 점화식을 정의하고 점화식을 이용하여 코딩하면 된다