문제출처: https://programmers.co.kr/learn/courses/30/lessons/42896?language=java
코딩테스트 문제를 풀다가 꽤 재밌는 문제를 발견해서 이 문제를 통해 Dynamic Programming을 정리하려고 합니다.
문제설명
카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.
각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.
- 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
- 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
- (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.
왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.
제한 사항
- 한 더미에는 1장 이상 2,000장 이하의 카드가 있다.
- 각 카드에 적힌 정수는 1 이상 2,000 이하이다.
재귀함수로 푸는 방법
우선 가장 쉽게 생각해낼 수 있는 재귀함수로 푼 코드입니다. 모든 경우의 수를 찾기 때문에 정확성은 맞지만 효율성은 떨어집니다.
class Solution {
private int[] left;
private int[] right;
public int solution(int[] left, int[] right) {
this.left = left;
this.right = right;
return helper(0,0);
}
public int helper(int leftInd, int rightInd) {
if (left.length == leftInd || right.length == rightInd) {
return 0;
}
if (right[rightInd] < left[leftInd]) {
int currAns = helper(leftInd, rightInd+1) + right[rightInd];
return currAns;
}
else {
int currAns = Math.max(helper(leftInd + 1, rightInd + 1),
helper(leftInd + 1, rightInd));
return currAns;
}
}
}Memoization (Top-down Approach)
다음은 위의 재귀적으로 푼 코드에서 memoization을 더해서 효울성을 높인 코드입니다. Memoization은 발음에서 느껴지는 것처럼 memorization과 같은 일을 하는데 만약 어떤 특정 인덱스에서의 최적값을 찾았다면 memoization 테이블에 저장해둠으로써 해당 인덱스에 대한 계산을 그만하도록 해서 실행속도를 빠르게 해주는 기술입니다.
class Solution {
private int[][] memo; // memoization 테이블
private int[] left;
private int[] right;
public int solution(int[] left, int[] right) {
memo = new int[left.length][right.length];
for (int i = 0; i < left.length; i++) {
Arrays.fill(memo[i], -1);
}
this.left = left;
this.right = right;
return helper(0,0);
}
public int helper(int leftInd, int rightInd) {
if (left.length == leftInd || right.length == rightInd) {
return 0;
}
if (memo[leftInd][rightInd] != -1) {
//이미 최적값을 찾은 상태
return memo[leftInd][rightInd];
}
if (right[rightInd] < left[leftInd]) {
// 오른쪽 카드가 더 작다면 오른쪽 카드를 버리고 더해준다
int currAns = helper(leftInd, rightInd+1) + right[rightInd];
// 계산한 값을 memoization 테이블에 저장
memo[leftInd][rightInd] = currAns;
return currAns;
}
else {
// 왼쪽카드만 버리거나 오른쪽카드와 왼쪽카드를 둘다 버리고 그 둘중 최적값을 계산
int currAns = Math.max(helper(leftInd + 1, rightInd + 1),
helper(leftInd + 1, rightInd));
// 최적값을 memoization 테이블에 저장
memo[leftInd][rightInd] = currAns;
return currAns;
}
}
}Bottom-up Approach
마지막으로 Bottom-up 방법으로 푼 코드인데 이 방법은 가장 Base 케이스부터 테이블을 채워나가는 방법입니다. Memoization 까지는 어느정도 쉽게 생각이 나는데 Bottom-up Approach는 아직 숙달이 안되서 그런지 방법이 잘 떠오르지 않네요. Dynamic Programming에 대해 잘 설명한 동영상이 있어서 하단에 링크를 걸어놓겠습니다.
class Solution {
public int solution(int[] left, int[] right) {
int[][] dp = new int[left.length + 1][right.length + 1];
for (int i = left.length - 1; i >= 0; i--) {
for (int j = right.length - 1; j >= 0; j--) {
if (left[i] > right[j]) dp[i][j] = dp[i][j + 1] + right[j]; //오른쪽 카드가 더 작다
else dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
}
}
return dp[0][0];
}
}