알아야할 개념
- 동적계획법(DP)
- 메모이제이션(Memoization)
dp
-
dp의 시작은 중복되는 부분이 있냐, 그리고 큰문제를 작은 단위로 나눌수있느냐? 로 시작할 수 있다.
- 그래서 동일한 작은 문제들을 반복하면 큰문제를 해결하는 방법이다.
-
하지만, 이부분만으로는 dp라고하기 어렵다. 중복되는 계산 결과를 저장하지않으면, 전에 했던 과정들을 다시 시작해야되기 때문에, 이미 했던 과정을 반복하지않기위해 저장하는 메모이제이션(
Memoization) 이 꼭 들어가줘야한다.
풀이과정
DP문제가 아닌 knapsack(배낭) 문제인 이유
단순히 DP문제라 하면, 누가봐도 반복이 눈에 보이는 문제이며, 이후 작은 단위의 선택지가 보이는 경우가 대부분이다.
- 대표적인 DP 문제들 예시
이렇게 직관적인 DP문제들을 반복되는 구간을 명시적으로 보여준다.
하지만, knapsack(배낭) 문제의 경우 반복적인 부분이 겉으로 드러나있지 않기때문에 내가 그 반복적인 부분을 찾아야 된다는것이다.
knapsack(배낭) 문제의 "반복적인 부분"
결국 중요한 부분은 선택지가 배낭에 물건을 "담는다" 와 "안담는다" 라는 점에 초점을 맞춰야한다는 것은 OK 알겠다. 하지만 DP배열은 어떻게 만들어야할까?
무게의 제한이라는 조건이 있기때문에 어려워진것이다.
그럼 무게제한이 없다고 생각하면 어떻게 될까?
무게 제한이 없을 경우
무게 제한이 없다면 사실 배낭에 모든 물건을 다 넣으면 되지만, 이해를 위해 담을 경우와 담지않을 경우로 나눠보자
| 무게 | 가치 |
|---|---|
| 1KG | 20 |
| 2KG | 10 |
| 3KG | 40 |
| 4kG | 30 |
- 배낭의 물건을 담을 수 있는 경우는
0~4개 가 된다. 이걸 N이라 하자 - 그리고 현재 배낭의 무게를
W라 하자 그럼0~10이 된다. - 이걸 표로 그리고
가치를 표현해보고자한다.
그럼 이걸 표로 그리면, 아래처럼 된다.
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | |||||||||||
| 1 | |||||||||||
| 2 | |||||||||||
| 3 | |||||||||||
| 4 |
- 우리가 최종적으로 알아내야할 것은 N=4일때,W=10일때,나올수있는 최대의 가치이다.
초기값 넣기
- 여기서 물건의 갯수가 0일때와, 배낭의 무게가 0일때는 아무것도 담을 수 없으므로 표안에 0의 가치를 매길 수 가 있다.
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | ||||||||||
| 2 | 0 | ||||||||||
| 3 | 0 | ||||||||||
| 4 | 0 |
1개만(1KG) 넣기
- 먼저 N= 1일때 부터 보자, N이 1일때는 한개의 물건을 담을 수 있다.
- 그리고 W를 1부터 10까지 쭈욱 차례대로 넣어보자
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | ||||||||||
| 3 | 0 | ||||||||||
| 4 | 0 |
- 먼저
1KG물건의 가치는20이고,2KG물건의 가치는10이다. - 그럼으로 갯수가
1이고 무게가2일때 나올수 있는 최고의 가치는 Math.max(20,10) =20이 나오게 만드는 것이다.
2개만(1KG, 2KG) 넣기
-
이제부터는 2개를 넣을 수 있다.
-
2개의 값을 물론 처음부터 계산해도 되지만, 기존에 계산한 것들을 활용하여 넣어보자.(중요!!!)
- N=2, W=1~2,의 경우는 W 때문에 2개를 가져다 넣을 수가 없다.
- 즉, (
현재 가능한 무게 - 담을 무게) < 0 - dp[2][1], dp[2][2] 에는 추가로 담을 수 없으니, 기존에 1개만 담았을때 최고의 가치값을 넣어줄 수 있다.
dp[2][1] = dp[1][1],dp[2][2] = dp[1][2]
먼저 위에 식이 이해가 되야한다. 추가로 담을 수 없으니, 기존의 최고의 가치값으로 넣어준다는 것! 이것이 담는다 안담는다 선택지중에
"안담는다"이다!
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | ||||||||
| 3 | 0 | ||||||||||
| 4 | 0 |
- 물론 위의 경우는 못담는다가 맞는 표현이지만, 결국 행위는 "안담는다" 로 포괄할 수 있다.
- 그다음
N=2,W=3의 경우를 봐보자 - 무게가 3KG이기에, 담을수 있는 경우의 수는 (1KG,2KG)가 가능해진다.
N=1 W=1에서 +2KG를 추가한 경우N=1 W=2에서 +1KG를 추가한 경우
- 이 것을 식으로 바꾸면 아래와 같다.
- dp[2][3] = Math.max(dp[1][1] + 2KG의 가치, dp[1][3]);
- dp[2][2] = Math.max(dp[1][2] + 1KG의 가치, dp[1][3]);
즉, 좀더 코드화하면
for(int i=1; i<=n; i++){
int weight = jewels[i].weight;
int value = jewels[i].value;
for(int j=0; j<=w; j++){
if(j >= weight) //추가로 담는 물건의 무게가 넘어가지 않는다면,
dp[i][j] = Math.max(dp[i-1][k]+ value[j-k], dp[i-1][j])
else{ //무게가 넘어가기때문에 이전의 최대값을 넣는다.
dp[i][j] = dp[i-1][j];
}
}
}| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | 30 | 30 | ||||||
| 3 | 0 | ||||||||||
| 4 | 0 |
- 그다음
N=2, W=4의 경우에도 (1KG,2KG)가 가능하다. - 결국
W=10까지 똑같이 적용하면 아래와 같이 된다.
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 |
| 3 | 0 | ||||||||||
| 4 | 0 |
3개(1KG, 2KG, 3KG)만 넣기
- 위 방식으로 3개일 경우도 진행한다.
- 하지만 이번엔
N=3 W=3일 경우 조금 달라진다.- (1KG, 2KG)의 경우와 (3KG)의 경우가 생기기 때문이다.
- dp[3][3] = Math.max(dp[2][0] + 3KG의 가치, dp[2][3]);
- dp[2][3] : (1KG,2kG)를 담은 경우
- dp[2][0] + 3KG의 가치 : 3KG만 담은 경우
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 |
| 3 | 0 | 20 | 20 | 40 | |||||||
| 4 | 0 |
- 이후에
W=4일경우엔- 1KG + 3KG =
60이 제일 큰 가치기에 값이 들어가고
- 1KG + 3KG =
W=5일경우엔- 2KG + 3KG =
50도 가능하나 - 1KG + 3KG =
60여전히 이값이 큰값이기에 들어간다.
- 2KG + 3KG =
W=6이후엔 3가지가 담을 수 있기에70으로 값이 들어간다.
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 |
| 3 | 0 | 20 | 20 | 40 | 60 | 60 | 70 | 70 | 70 | 70 | 70 |
| 4 | 0 |
4개만 넣기
- 위 방식으로 4개일 경우도 진행
| N\W | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | 30 | 30 | 30 | 30 | 30 | 30 | 30 | 30 |
| 3 | 0 | 20 | 20 | 40 | 60 | 60 | 70 | 70 | 70 | 70 | 70 |
| 4 | 0 | 20 | 20 | 40 | 60 | 60 | 70 | 70 | 90 | 90 | 100 |
무게 제한이 있을 경우
예를 들어 무게 제한이 5KG라고 해보자
- 무게 제한이 생겼다고 해서 달라질건
배열의 크기밖에 없다. - 무게제한이 넘어가지 않는다면
- dp[i][j] = Math.max(dp[i-1][k]+ value[j-k], dp[i-1][j])
- 무게 제한이 넘는다면
- dp[i][j] = dp[i-1][j]
- 위 w=10인 배열에서 5인 배열로 바뀐것일뿐 값은 동일하다.
| N\W | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 20 | 20 | 20 | 20 | 20 |
| 2 | 0 | 20 | 20 | 30 | 30 | 30 |
| 3 | 0 | 20 | 20 | 40 | 60 | 60 |
| 4 | 0 | 20 | 20 | 40 | 60 | 60 |
마무리
- 처음 배낭문제를 보았을때, 왜 DP로 푸는지 제대로 이해가 되질 않았다.
- 처음 DP 2차원 배열을 만드는 것부터 이해가 안되다보니 하향식으로 거꾸로 접근하여 풀어가는 방식도, 점화식을 만들어가는 방식도 찜찜하게 알게되는 느낌이 생겨, 나는 왜 2차원 배열로 푸는 걸까?에 초점을 맞추게되었고, 자연스럽게 이 의문을 풀기위해서 조건을 하나 없애보았다.
- 그러니까 자연스럽게 W의 배열의 역할과, N의 배열의 역할이 보이게되면서 여태봤던 레퍼런스들이 이해가 되었다.
아는 만큼 보이는게 맞는 것 같다. 나처럼 dp배열부터 이해가 안가시는 분들이 직접 파헤쳐보시면서 이해가 되셨으면 좋겠으며, 저처럼 한 걸음 더 나아간 느낌이 들었으면 한다.
