12. 동적계획법(Dynamic Programming)

  프로그래밍 문제해결에서 가장 많이 쓰이는 코딩 스킬 중 하나인 "동적 계획법(Dynamic Programming)"에 대해 알아볼 시간이다. 이름에서 알 수 있듯이 알고리즘이 아는 프로그래밍 방법이라고 생각하면 좋다. 하지만, 알고리즘 시간에 소개하는 이유는 워낙 많이 쓰이기도 하고, 앞서 배웠던 Conquer 알고리즘의 응용 버전이기 때문이기도 해서 이번 시간에 소개를 할 생각이다.

  우리 모두 피보나치 수열이 무엇인지는 알고 있을 것이다. 피보나치 문제를 푸는 가장 좋은 방법은 반복해서 풀어낸다. 코드로 작성하기도 매우 쉽고 직관적으로도 이해가 잘 된다. 피보나치 수열을 recursive 하게 풀어낸다면 아래와 같은 코드를 작성하게 될 것이다.

import java.util.Scanner;
 
public class Solution {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        
        System.out.println(fibo(a));
 
    }
    
    static int fibo(int a){
        if (a==1||a==0) return 1; 
        return fibo(a-1)+fibo(a-2);
    }
 
}

 

  코드도 20줄 이내로 작성 될 만큼 매우 간단하고, 직관적으로도 이해가 빠를 것이다. 하지만, 재귀 방식의 단점은 무엇일까? 함수를 연속적으로 불러야 하기 때문에 컴파일러는 해당 코드를 읽을 때 수많은 오버헤드가 발생될 것이다. 숫자가 작다면 큰 의미가 없겠지만, 네자리, 다섯 자리 넘어가게 된다면 메소드를 부르기 위해 Stack에 명령이 쌓일 것이고, 쉽게 Stack Overflow가 발생한다. 이 문제를 해결하기 위해 고안된 방법이 바로, 동적 계획법이다.

1. 동적 계획법이란?

  동적 계획법을 한마디로 쉽게 정의 한다면, 이전에 구한 답을 다시 가져오는 방법이다. 반복적으로 메소드를 불러오는 횟수를 줄이고 추가 공간에 과거에 구한 답을 저장하여 그보다 큰 답이 무엇인지를 구한다. 이런 점에서 동적 계획법은 분할 정복 알고리즘과 매우 유사하다. 말로 설명하는 것보다 직접 원리를 이해해보자.

  피보나치 수열에서 시작 항을 fibo(0)=0, fibo(1)=1로 가정하자. 즉, fibo(2)는 1이고 fibo(3)은 2로 증가하도록 피보나치 수열을 정의하였다. 

해당 fibo의 수를 구하기 위해서 일정 공간을 지는 배열에 해당 값을 입력한다. 일정 공간을 총 50개라고 가정을 하자. 그리고, 50개에 해당 하는 값을 반복문을 활용해 저장한 뒤 구하고자 하는 항이 몇인 지를 출력해 내는 방식이다.

import java.util.Scanner;
 
public class Solution {
    
    static int[] fibo_memo;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        
        fibo_memo = new int[45];
        fibo(a);
 
    }
    
    static void fibo(int a){
        
        fibo_memo[0]=0;
        fibo_memo[1]=1;
        
        for(int i=2; (i<=a)&&(i<45); i++){
            fibo_memo[i]=fibo_memo[i-2]+fibo_memo[i-1];
        }
        
        System.out.println(fibo_dp(a));
    }
    
    static int fibo_dp(int a){
        if(a<45) return fibo_memo[a];
        else{
            return fibo_dp(a-1)+fibo_dp(a-2);
        }
        
    }
 
}
 

  fibo_memo라는 배열을 생성하여 피보나치 함수 값을 미리 구하여 저장하였다. 그 크기를 45로 지정하였는다. Java 컴파일러에서 허용된 int의 범위값을 저장 할 수 있는 범위가 피보나치 수열의 45항이기 때문에 위와 같이 설정했다. 만약 이보다 더 큰수를 구하는 프로그래밍이 필요하다면 변수 값을 int가 아닌 다른 변수로 지정해야한다. 이런 과정으로 동적 계획법을 이용한 피보나치 수열 프로그램을 만들었다. 재귀 함수로 푼 피보나치의 시간 복잡도는 O(2^n)이다. 재귀 함수를 이용한 방법의 도표를 그린다면 시간 복잡도가 왜 저렇게 나오는지 이해하기가 쉽다. 3인 경우 총 8번의 연산을, 4인 경우 총 16번의 연산을 실시한다. 반면 동적 계획법의 시간 복잡도는 O(n^2)이다. 

  동적 계획법은 연산을 크게 줄이는데 매우 유리하나, 그만큼의 불리함도 2가지 존재한다. 첫 번째는 한정적인 공간이다. 재귀 방식은 컴파일러가 매우 뛰어나고 연산 속도가 빠르고 Stack Overflow를 막을 수 있다면 무한대로 원하는 결과 값을 얻어낼 수 있다. 값을 입력하고 곧바로 구해내기 때문에 아무리 큰 숫자가 와도 문제를 해결할 수 있다. 물론, 이 세상에 그런 컴퓨터는 존재하지 않는다. 그리고, 추가 공간이 필요하다는 점이다. 메모리가 필요없는 재귀 방식에 비해, DP는 추가 공간이 필요하다는 불편함이 존재한다.

2. 거스름돈 문제

  이번에는 DP를 활용하여 조금 더 실용적인 문제를 작성해보자. 가령 7840원짜리 물건을 사기위해 1만원을 지불했다면 우리는 거스름돈으로 2160원을 받아야 할 것이다. 다행히 대한민국의 동전 체계는 5의 배수로 증가하기 때문에(10원, 50원, 100원, 500원)직관적으로 500원 짜리 동전 4개, 백원짜리 1개, 50원짜리 1개, 10원짜리 1개를 줘야 된다는 정보를 쉽게 알 수 있다. 정확히 표현하면 Greedy 알고리즘을 활용하여 구할 수 있다. 하지만, 우리나라 동전 체계가 10원, 30원, 40원으로 구성되어 있다고 가정하면 상당히 구하기 어려워진다. 이런 이상한 나라가 하나 있다고 생각해보자. 이 때, 최소의 개수로 동전을 지급하는 방법에 대해 구해보자.

  우선 거스름돈이 10원인 경우 무조건 10원짜리 동전 한개를 지불해야 한다. 마찬가지로 거스름돈이 30, 40원이라면 각각의 동전 한개를 지불하면 된다. 그 이상의 동전을 지급해야 한다면 어떻게 하면 좋을까, 지불해야 하는 금액 기준으로 10원, 30원, 40원 덜 지불하는 경우 중에서 최소값을 구하면 된다. 50원을 지불해야 하는 케이스라면 50원에서 10원, 30원, 40원을 빼서 지불해야하는 동전 개수 중 최소값이 무엇인지를 구하고, 해당 개수에서 동전을 1개 증가 시키면 지불이 쉽다. 물론, 각각의 동전을 무한대로 있다고 가정하자.

  이를 구한 Pseudo Code는 아래와 같을 것이다.

  이번에는 Java 언어를 활용해 해당 알고리즘을 구현해보자.

import java.util.Scanner;
 
public class Solution {
    
    static int[] change;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        Scanner sc = new Scanner(System.in);
        
        change = new int[100];
        
        System.out.println("거스름돈을 입력해주세요:");
        int i = sc.nextInt();
        
        calc_change();
        
        System.out.println("지불해야하는 거스름돈 개수 :" + change[i]);
 
    }
    
    static void calc_change(){
        change[0]=0;
        
        for(int i=1; i<100; i++){
            change[i] = min_change(i)+1;
        }
        
    }
    
    static int min_change(int i){
        int min = change[i-1];
        if(i>=3){
            if(min>change[i-3]) min = change[i-3];
        }
        if(i>=4){
            if(min>change[i-4]) min = change[i-4];
        }
        return min;
    }
 
}
 

  동전에 1,3,4원이 존재한다고 가정하고, 배열의 크기를 100으로 해 100원까지의 거스름돈의 개수를 위와 같은 프로그래밍으로 쉽게 구할 수 있다. 공간의 크기가 100인 배열이 존재한다면 값을 쉽게 구해낼 수 있다.

3. Knapsack 문제

  이번엔 당신이 보따리 장수라고 가정해보자. 그리고 당신에겐 10kg의 물건을 담을 수 있는 가방이 있다. 그리고 팔 수 있는 물건은 7kg 42달러 물건, 3kg 짜리 12달러, 4kg 짜리 40달러, 5kg 짜리 25달러가 존재한다. 최대의 이익을 구하기 위해서 어떤 방법으로 짐을 챙기는 것이 좋을 지 생각해보자.

  첫 번째 방법은 무적의 알고리즘인 Brute Force를 사용하면 된다. 물건을 구할 수 있는 부분 집합을 모두 구하면 된다. 하지만 물건의 개수가 증가하게 된다면 시간 복잡도 역시 무한대로 증가한다. 상품의 개수가 n개라면 시간 복잡도는 O(2^n)으로 상당히 나쁜 알고리즘이 나오게 된다.

  DP를 사용하여 조금 쉽게 문제를 해결해보자. 무게는 0~10까지 가능하고, 이에 따라 값이 정해진다. 가방의 용량이 10Kg이고, 해당 범위 안에서는 물건을 자유롭게 담을 수 있다. 이를 이용해 무게 X 물건의 Table을 만들어 낼 수 있다.

 

  아이템 1번 7kg, 2번 3kg, 3번 4kg, 4번 5kg라고 했을 때, Item 행은 물건을 하나씩 추가 하면서 최대 무게 Weight일 때 나오는 최대의 무게를 구하는 방법이다. F(i,j)라고 할 때 F(2,7)은 가방에 7kg의 물건을 담았고, 상품으로 7,3kg 두개의 물건을 사용 했을 때 구할 수 있는 최대 값이다. 아이템 하나를 추가하기 전과 이전의 값을 비교하여 큰 값을 Table에 채우는 방법으로 문제를 해결 할 수 있다. 해당 알고리즘은 아래와 같은 Pseudo Code 로 표현 가능하다.