동적 설계법 - 값을 기억해서 재활용한다. -1

동적 설계법(DP : Dynamic Programming)이란 알고리즘 설계 기법의 하나로서 프로그래밍 콘테스트에서 매우 자주 출제됩니다. 

탐색 메모화 및 동적 설계법

베낭문제(Knapsack problem)

무게와 가격이 각각 wi, vi인 n개의 물건이 있습니다. 무게의 총합이 W를 초과하지 않도록 물건을 선택했을 때 가각 총합의 최대치를 구하세요.

예)

입력

n = 4

(w, v) = {(2, 3), (1, 2),(3, 4), (4, 9)}

W = 7

출력 

14 ( 4, 0, 2 번 물건을 고른다)

이것은 배낭 문제라고 불리는 유명한 문제입니다. 이 문제는 어떻게 접근하면 좋을까요? 우선 일반적인 방법으로 생각해보면 (넣는다/안 넣는다) 이 두 가지 상태로 분기하면서 탐색하는 방법을 생각할 수 있습니다. 

코드로 보면 다음과 같습니다.

public class Knapsack_Recursive1 {
    int[] w = {2, 1, 3, 4};
    int[] v = {3, 2, 4, 9};
    int MAX_ITEM_LENGTH = w.length;
    int MAX_ITEM_WEIGHT = 7;


    int cnt = 0;
//    i : 아이템의 인덱스
//    j : 무게의 총합. MAX 값으로 시작해서 아이템을 선택하여 넣는다 이면 해당 아이템의
//    무게를 뺀다.
    public int recursive(int i, int j){
        cnt++;
        int res = 0;
        if(i==MAX_ITEM_LENGTH){
            res = 0;
        }else if(j<w[i]){
            // 이 물건은 무게의 총합보다 크므로 패쓰한다.
            res = recursive(i + 1, j);
            // 다음번 인덱스로 넘기고, 무게의 총합은 변하지 않는다.
        }else {

//            넣었을 때,  넣지 않았을 때를 조사한다.
//            max(넣지 않았을 때, 넣었을 때)
//            넣었을 때의 수식을 말로 풀어쓰면
//            현재 아이템의 값을 더하고, 무게를 제거한다.
            res = max(recursive(i+1, j), recursive(i+1, j-w[i])+v[i]);
        }
        return res;
    }

    int max(int a, int b) {
        return Math.max(a, b);
    }

    @Test
    public void test(){
        System.out.println(recursive(0, MAX_ITEM_WEIGHT));//14
        System.out.println(cnt);//28
    }
}

이 방법은 탐색의 깊이가 n이고, 각 깊이에 대해 2회 분기처리 하므로 최악의 경우 O(2^n) 시간이 걸리므로 n 값이  크면 지나치게 많은 시간이 걸리므로 좋은 방법이라 할 수 없습니다.

메모화 테이블을 활용할 수 있다.

mt[아이템 갯수][최대 담을 수 있는 무게]

테이블을 만든다.

그리고 이미 계산한 값이라면 계산된 값을 리턴하는 것이다.

public class Knapsack_Recursive2 {
    int[] w = {2, 1, 3, 4};
    int[] v = {3, 2, 4, 9};
    int MAX_ITEM_LENGTH = w.length;
    int MAX_ITEM_WEIGHT = 7;
    // memorize table
    int[][] mt = new int[MAX_ITEM_LENGTH+1][MAX_ITEM_WEIGHT+1];

    int cnt = 0;
//    i : 아이템의 인덱스
//    j : 무게의 총합. MAX 값으로 시작해서 아이템을 선택하여 넣는다 이면 해당 아이템의
//    무게를 뺀다.
    public int recursive(int i, int j){

        cnt++;
//        함수에 같은 parameters가 전달된다면 같은 결과가 나오므로
//       이미 조사한적이 있는 parameters라면 이전 값을 활용한다.
        if(mt[i][j]>0) return mt[i][j];

        int res = 0;
        if(i==MAX_ITEM_LENGTH){
            res = 0;
        }else if(j<w[i]){
            // 이 물건은 무게의 총합보다 크므로 패쓰한다.
            res = recursive(i + 1, j);
            // 다음번 인덱스로 넘기고, 무게의 총합은 변하지 않는다.
        }else {

//            넣었을 때,  넣지 않았을 때를 조사한다.
//            max(넣지 않았을 때, 넣었을 때)
//            넣었을 때의 수식을 말로 풀어쓰면
//            현재 아이템의 값을 더하고, 무게를 제거한다.
            res = max(recursive(i+1, j), recursive(i+1, j-w[i])+v[i]);
        }
        mt[i][j]=res;
        return res;
    }

    int max(int a, int b) {
        return Math.max(a, b);
    }


    void initMt(){
        for(int i=0;i<MAX_ITEM_LENGTH;i++)
            for(int j=0;j<MAX_ITEM_WEIGHT;j++)
                mt[i][j]=-1;
    }
    @Test
    public void test(){
        System.out.println(recursive(0, MAX_ITEM_WEIGHT));//14
        System.out.println(cnt);//26
    }
}

이렇게 함으로해서 recursive 함수를 28번에서 26번 방문하는 것으로 줄었다.

최악의 경우에도 O(n*W) 로 되었다.

메모화 테이블에 주목해 보도록하겠다. 

다음 글에서 계속.

예제 출처) 프로그래밍 콘테스트 챌린징(http://www.roadbook.co.kr/49)