[코딩테스트] 동적계획법과 냅색(Knapsack) 문제

인프런 김태원 님 강좌를 듣고 정리한 내용입니다. 

냅색 문제?

짐 싸기 문제 또는 배낭 문제라고 불리며 범위가 늘어날수록 시간초과의 위험이 있어 DP(동적 계획법)으로 푸는 경우가 많다.

 

서로 다른 가치를 지닌 보석의 종류가 주어지고 가방에는 담을 수 있는 무게제한이 있을 때 보석을 최대한의 가치로 가방에다 담는 문제로 많이 출제된다.

 

즉, 여러 물건이 있을 때 특정한 조건을 만족하는 조합을 구하는 문제이다.

 

강의에서는 두가지 방법으로 냅색문제를 푸는 방법을 제공한다.

1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터 해결한다.
2. 개수가 정해져 있을 때, 종류마다 한 개씩 존재, 유한개면 뒤에서부터 해결한다. 

강의에 나온 예제를 두가지 방법으로 각각 풀어보자.

 

1. 동전교환(최소갯수 구하기) 

설명

다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해 주려면 어떻게 주면 되는가?

각 단위의 동전은 무한정 쓸 수 있다.

 

입력

첫 번째 줄에는 동전의 종류개수 N(1<=N<=50)이 주어진다.

두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1 <=M <=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

 

출력

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

 

예시 입력 1 

3
1 2 5
15

예시 출력 1

3

 

구현코드

public class Problem_5 {
    public int solution(int n, int m, int[] coin) {
        int[] dp = new int[m+1];
        
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for(int i = 0; i < n; i++){
            for(int j = coin[i]; j <= m; j++){
                dp[j] = Math.min(dp[j], dp[j-coin[i]] + 1);
            }
        }

        return dp[m];
    }
    
    public static void main(String[] args){
        Problem_5 T = new Problem_5();
        System.out.println(T.solution(3,15,new int[]{1,2,5}));
    }
}

이 문제는 앞서 이야기했던 1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터 해결한다. 을 활용해야 한다. 

 

그 전에 동적계획법으로 풀기 위한 조건인 dp배열과 점화식을 찾아야한다. 강의에서는 냅색문제를 풀 때 1차원 배열을 dp배열로 선언해 푸는 방법을 알려준다. 

 

문제에선 거슬러 줄 금액이 무게 제한이 있는 가방이므로 dp배열이 된다. 0~15까지 인덱스를 가진 dp[m+1] 를 선언해 주면 된다. 

dp[i]는 i 금액을 만드는 데 사용되는 최소동전 개수이다.

다음은 냅색 문제의 점화식을 구하는 방법이다. 

 

초기 dp 배열은 dp[0] = 0, 최솟값을 구하는 것이므로 나머지는 무한대(코드구현은 구분할 수 있는 큰 값)로 초기화한다. 

coin[0] 일 때는 1원이므로 1 ~ 15까지 반복하며 해당 동전으로 금액을 채울 수 있는 개수로 초기화하며, 기존값보다 작으면 값이 바꿔준다.

coin[1] 일 때는 2원이므로 2 ~ 15까지 반복하며 아래와 같은 배열이 완성된다.

여기서 점화식을 유추할 수 있습니다. index 2부터 시작하며 2원의 동전을 한 개를 사용한다고 가정하자. 그럼 기존값에서 2원을 빼는 거니깐 dp[ j - coin[i]] 를 유추 할 수 있습니다. 그런 다음 +1 해주는 것은 해당 동전을 사용하기 때문이다. 

 

dp[ j - coin[i]] 을 좀 더 설명하면 만약 2원으로 5원을 만든다고 가정하면 2원을 하나 사용한다는 전제하에  5원에서 2원을 빼고 남은 3원을 최소개수가 dp[3]에 있으니 dp배열 인덱스 선언부에서 계산이 이루어진다.

 

결론적으로 점화식은 각 동전 종류를 사용하여 최솟값을 구하는 것이므로 

dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1) 

표현할 수 있다. 

 

정리하자면 1번 방법은 coin[i] ~ m까지 순차적으로 진행되기 때문에 "앞에서부터 해결한다"라고 표현한다.  

 

2. 최대 점수 구하기 

설명

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는 데 걸리는 시간이 주어지게 됩니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.

(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한 개만 풀 수 있습니다.)

 

입력

첫 번째 줄에 문제의 개수 N(1 <=N <=50)과 제한 시간 M(10 <=M <=300)이 주어집니다.

두 번째 줄부터 N 줄에 걸쳐 문제를 풀었을 때의 점수와 푸는 데 걸리는 시간이 주어집니다.

 

출력

첫 번째 줄에 제한 시간 안에 얻을 수 있는 최대 점수를 출력합니다.

 

예시 입력 1 

5 20
10 5
25 12
15 8
6 3
7 4

예시 출력 1

41

 

구현코드

public class Problem_6 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] dp = new int[m+1];

        for (int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int ps = Integer.parseInt(st.nextToken());
            int pt = Integer.parseInt(st.nextToken());
            //중복 방지를 위해
            for(int j = m; j >= pt; j--){
                dp[j] = Math.max(dp[j], dp[j-pt] + ps);
            }
        }

        System.out.println(dp[m]);
    }

}

이 문제는 위에서 이야기한 2. 개수가 정해져 있을 때, 종류마다 한 개씩 존재, 유한개면 뒤에서부터 해결한다. 를 이용하는 문제이다.

 

dp배열은 주어진 제한시간을 기준으로 하면 된다.  

dp[i] 는 i초의 최대점수가 기록된다. 

점화식을 구하면 되는데 1번 방법을 왜 사용하면 안 될까? 

 

첫 번째 조건값인 점수가 10, 초가 5인 경우로 확인해 보자.

5~9초까지는 초기값에서 10점을 더하니깐 10점이 최댓값으로 초기화된다. 

10번째 index를 확인해 보면 dp[10-5] + 10가 되므로 20이 되는데 그럼 10점을 중복사용하게 된다. 그래서 순차적으로 진행하는 1번 방법을 사용할 수 없는 것이다. 

 

그럼 2번 방법으로 점화식을 구해보자.

2번 방법은 뒤에서 부터 해결한다고 되어있으므로 제한 시간인 20 부터 시작한다. 20 부터 시작해 주어진 초시간까지 반복하면서 진행하면 된다. 

 

10, 5 일 때  20~5 범위를 뒤에서 부터 진행한다.

최대값을 구함으로 초기세팅은 0값이므로 주어진 10점으로 해당 범위 값이 초기화 된다.

마찬가지로  25, 12 일 때 20 ~ 12 범위를 뒤에서 부터 진행한다.

20초부터 시작해보면 12초를 한번 사용하는 것을 기준함으로 20-12 = 8 인 dp[8] 값과  사용한 12초의 점수 25점을 더한 35 값이 된다. 

이런식으로 진행하면 아래 배열에 가장 아래값처럼 초기화 된다.

냅색문제는 동일한 점화식 구조인 dp[j - pt] + ps 사용하며, 구한 점화식과 기존값 중에 최댓값을 구함으로 아래와 같은 식이 완성된다.

dp[j] = Math.max(dp[j], dp[j-pt] + ps)

 

정리하자면

해당 강의에서는 냅색문제를 풀 때, 1차원 dp배열을 이용해 접근하였다. 대부분 냅색문제에 대한 자료를 찾아보면 2차원 배열 형태로 푸는 경우가 많은데, 1차원으로 풀면 2차원 배열로 풀때보다 실행 시간에 이점을 가져갈 수 있다. 

 

냅색 문제의 점화식은 최소값을 구하느냐, 최대값을 구하는냐 그 차이만 있고 패턴은 같다는 것을 확인 할 수 있다. 

 

마지막으로 보석의 종류를 유한하게 사용가능한가 또는 무한개 사용 가능하냐에 따라 dp배열 탐색 순서가 달라질 수 있다정도만 고려하면 생각보다 쉽게 접근 가능하다.