냅색 알고리즘 이해하기
- 냅색 알고리즘은 조합 최적화 알고리즘이다.
- 주로 쪼갤 수 없는 요소들의 활용해 문제의 조건에 대한 조합의 최적화를 구할 때 사용한다.
동전 교환 문제
- 동전의 종류들과 거슬러 줄 금액이 주어질 때, 거슬러 줄 동전의 최소 갯수를 구해라!
위와 같은 문제가 있다고 해보자!
동전 종류와 거슬러줄 금액은 다음과 같다.
1 2 5
15
이런 동전 문제는 깊이 우선 탐색으로도 해결할 수 있지만, 동전의 종류가 50개가 넘어가는 문제에서는 너무 많은 시간이 소요된다.
동전의 종류와 같은 쪼갤 수 없는 요소들에 대한 조합 최적화를 구할 때 냅색 알고리즘을 사용하면 빠르게 문제를 해결할 수 있다.
냅색 알고리즘은 동적계획법 문제이기에 우선 서브 미션을 구해야 한다.
- 서브 미션 : 배열을 만들어 거슬러 줄 금액당 최소 동전의 갯수를 구하는 것을 서브 미션으로 지정하자!
-
최소 동전 갯수를 구해야 하는 문제이기에, 우선 배열을 최대값으로 모두 초기화한다.
-
그 후 배열의 인덱스 0에 해당하는 값은 0으로 초기화 한다.
(배열의 인덱스는 거슬러 줄 금액, 인덱스의 값은 거슬러 줄 동전의 최소 개수로 지정한다.)
-> 0원을 거슬러 줄때 거슬러줄 동전의 최소 개수는 존재하지 않기 때문이다. -
주어진 동전의 갯수를 무한으로 사용할 수 있기 때문에, 우선 1원만 사용하여 거슬러 줄 동전의 갯수 -> 즉 배열의 값들을 다시 초기화 해준다.
(배열 값들은 모두 거슬러줄 금액을 위해 1원이 총 몇개 필요한가로 초기화 되어있다.) -
다음은 2원을 사용할 경우인데, 이때는 1원과 2원을 모두 사용해서 배열을 변경한다.
2원을 사용할 경우는, 인덱스 2부터 배열을 순회하여 값을 초기화하면 되는데, 0원과 1원을 2원으로 거슬러 줄 수는 없기 때문이다.
그렇다면 2원부터는 어떻게 거슬러 줄 수 있을까?
우선 2원 부터 살펴보자.
2원은 0원을 거슬러 줄 경우의 동전의 최소 갯수와 2원을 1개 사용하는 경우을 더하면 된다. -> coin[0] + 1
3원은 1원을 거슬러 줄 경우의 동전의 최소 갯수와 2월을 1개 사용하는 경우을 더하면 된다. -> coin[1] + 1
.......
이를 반복하면 점화식을 구할 수 있는데, 점화식은 ***coin[idx - 2] + 1*** 로 나온다.그럼 이제 1원, 2원, 5원을 모두 사용하여 거슬러줄 돈을 구하는 과정을 정리해보자.
-
1원만을 사용하여 거슬러 주는 경우로 배열을 채운다.
-
2원도 사용하는 배열로 변경하는데, 이미 1원을 항상 사용하는 배열을 사용하고 있기에, index 2부터 1원 2개를 2원 1개로 변경하면서 배열을 하나씩 수정한다.
-
1원과 2원만을 사용하여 거슬러 줄 동전의 최소 갯수 배열에서 index 5부터 1원 1개를 2원 2개를 5원 1개로 변경하면서 배열을 하나씩 수정한다.
점화식 : coin[idx - 5] + 1
결국 최종 점화식은 coin[idx - i] + 1 로 나오는 것을 알 수 있다.
동전 교환 문제 소스 코드
public class 동전교환 {
static int n, m;
static int[] dy;
public int solution(int[] coin) {
Arrays.fill(dy, Integer.MAX_VALUE);
dy[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = coin[i]; j <= m; j++) {
dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
}
}
return dy[m];
}
}
최대 점수 구하기
동전 교환 문제의 경우 동전들을 무제한으로 사용하기 때문에, 배열의 인덱스를 1부터 순회하였다.
이와 달리 한정된 횟수가 존재하는 문제는 어떨까?
이번에는 단 1회만을 사용하는 경우에 대해 살펴보자.
문제 설명
제한된 시간안에 문제를 풀어 얻을 수 있는 최대 점수를 구하여라
입력 : 순서쌍으로 문제를 풀었을 때의 점수와 문제를 푸는데 걸리는 시간이 주어진다.
20 -> 제한 시간
10 5 -> 점수 / 푸는데 걸리는 시간
25 12
15 8
6 3
7 4- 위와 같은 문제는 문제가 모두 1개씩만 존재하기 때문에, 동전 교환과 같은 방법을 사용할 수 없다.
제한된 횟수가 존재하는 경우 기존에 인덱스가 1부터 시작한 것과 달리 가장 뒤에서 부터 시작해야 한다.
같은 냅색 알고리즘이기에 score[idx - 걸리는 시간] + 점수 를 사용한다.
우선 문제 푸는데 5분이 걸리고 10점을 주는 경우를 먼저 사용해 배열을 초기화 해보자.
동전 교환 문제는 최소 개수를 구하기 위해 최대값으로 배열을 초기화했다면, 최대 점수를 구해야 하는 문제는 0으로 배열을 초기화한다.
이후 배열의 값보다 더 큰 점수를 획득하면 값을 초기화 한다.
서버 미션의 경우 동전 교환 문제와 동일하다.
- 인덱스 : 제한된 시간
값 : 제한된 시간동안 획득할 수 있는 최대 점수
10점 문제를 풀었을 때, 제한된 시간이 20이니 인덱스 : 20 부터 채우면,
(인덱스가 5까지 순회)
인덱스 / 값
20 -> 10 점
19 -> 10 점
...
5 -> 10 점으로 배열이 구성된다.
이제 10점 문제와 25점 문제를 동시에 풀때를 계산해보자.
(인덱스가 12까지 순회)
인덱스 / 값
20 -> score[20 - 12] + 25 = 35 > 10 이므로 값이 35로 초기화 된다.
19 -> score[19 - 12] + 25 = 35 점
18 -> 35 점
17 -> score[17 - 12] + 25 = 35 점
16 -> score[16 - 12] + 25 = 25 > 10 이므로 값이 25로 초기화 된다.
...
5 -> 10 점최대 점수 구하기 문제 점화식 : score[idx - 시간] + 점수
최대 점수 구하기 소스 코드
public class 최대점수 {
static int n, m;
static int[] dy;
public int solution(int[] pt, int[] ps) {
Arrays.fill(dy, Integer.MAX_VALUE);
dy[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = m; j >= pt[i]; j--) {
dy[j] = Math.max(dy[j], dy[j - pt[i]] + ps[i]);
}
}
return dy[m];
}
}