[Algorithms] Dynamic Programming 개념과 구현

최근 알고리즘 문제를 풀면서 벽에 부딪히는 느낌이 많이 들었는데, 그 중 Dynamic Programming이라는 유형의 문제는 쉽게 감이 잘 잡히지 않는 유형 중 하나였다. 그럼에도 불구하고 Dynamic Programming은 중요한 알고리즘 디자인 패러다임이기에 한 번 제대로 이해하고 문제도 풀어볼 가치가 있다.

Dynamic Programming

---

• 사실 Dynamic Programming 이름만 가지고는 다른 "이분 탐색", "분할 정복", "너비 우선 탐색"과 같이 무엇을 의미하는 잘 다가오지 않는데, Dynamic Programming이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며 전산학 전반에서 일반적으로 사용하는 Dynamic, 혹은 Programming이란 단어와는 아무런 관련이 없다고 한다. 즉 최적화 문제를 풀기 위한 기법이라고 보면 된다.

Dynamic Programming

중복 부분 문제

---

• Dynamic Programming은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 가령 분할 정복은 주어진 문제를 쪼개서 Subproblem을 만들어 계산을 한 후 점점 합치는 과정인데, 동적 계획법도 Subproblem을 만든다는 점에서 비슷한 면이 있지만 결정적으로 분할 정복과의 차이는 바로 Subproblem을 만드는 방식이다.

Dynamic Programming Subproblem

• Dynamic Programming은 분할 정복과 달리 Subproblem을 두 개 이상의 문제를 푸는 데 사용할 수 있기에, 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 "재사용"함으로써 속도의 향상을 꾀할 수 있게 된다. 즉 Overlapping Subproblem 문제를 해결하는 기법이라고도 볼 수 있다.
  • 그래서 Dynamic Programming에서는 계산 결과를 cache에 저장해 사용함

Overlapping Subproblem

---

• Overlapping Subproblem이라는 말이 별로 와닿지 않을 수 있는데, Overlapping Subproblem이 발생할 수 있는 가장 쉬운 예시로 재귀 호출을 이용한 이항 계수를 구하는 문제를 보면 되는데 이항 계수는 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수이다.
• 그리고 이항 계수를 재귀 함수로 구현한 코드는 아래와 같다.

public int bino(int n, int r) {
    if (r == 0 || n == r) {
                return 1;
        }
        return bino(n-1, r-1) + bino(n-1,r);
}

• 위 재귀 함수 동작 자체는 큰 문제가 되지 않다. 하지만 위 코드의 Overlapping Subproblem가 발생하기 때문에 n, r이 커짐에 따라 성능에 급격한 영향이 갈 수 있다.

https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

• 위 코드를 실행하면 위와 같이 동작이 실행이 되는데, 잘 살펴보면 부분 문제를 나눠서 계산하는 과정에서 Overlapping Subproblem이 발생하고, 그리고 재귀의 깊이기 깊어짐에 따라 Overlapping Subproblem의 빈도 수가 늘어남을 파악할 수 있다.
• 그래서 위와 같은 문제는 Dynamic Programming을 통해 Memoization을 구현해 해결할 수 있게 된다.

Dynamic Programming Memoization

---

• Dynamic Programming에서의 Memoization은 한 번 계산한 결과를 저장해 뒀다 "재활용"하는 기법이다. 즉 Overlapping Subproblem이 발생하는 부분을 Memoization을 통해 재활용한다고 보면 된다.

이항 계수 Memoization 적용

private cache[30][30];

public int bino2(int n, int r) {
    if (r == 0 || n == r) {
                return 1;
        }

        if (cache[n][r] != 0) {
                return cache[n][r];
        }
        return cache[n][r] = bino(n-1, r-1) + bino(n-1,r);
}

• 위와 같이 Memoization을 적용하게 된다면, bino에서 발생한 Overlapping Subproblem을 캐시에 저장한 후 호출 시 반환 함으로써 함수 호출 횟수가 엄청나게 감소한다.
• 즉 이와 같이 Memoization을 활용해 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법을 Dynamic Programming라고 한다.

Memoization 구현 조건

---

• 그럼 Overlapping Subproblem가 발생하면 모두 Memoizaion을 구현하면 되는 것은 아니다.
• 위 이항 계수 문제를 잘 살펴보면 함수의 반환 값은 입력의 값만으로 결정 되는데, 이런 경우에 Memoization을 사용할 수 있게 된다. 만약 반환 값이 입력의 값이 아닌 다른 클래스 멤버 변수 혹은 전역 변수에 의해 결정이 된다면 Memoizaion을 통해 저장된 값의 투명성이 깨지기 때문이다.
  • 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성이라고 한다.
• 즉 Memoization은 참조적 투명 함수의 경우에만 적용할 수 있고 외부 요소에 따라 다른 값이 반환된다면 캐싱을 할 수 없게 된다.

Dynamic Programming 풀이 전략

---

• Dynamic Programming 개념 자체는 그리 어렵지 않고, 실제 구현 로직은 아래와 같이 간단하다.

일반적인 Dynamic Programming

• 주어진 문제를 완전 탐색을 이용해 해결
• 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용.

최적화 문제 Dynamic Programming

• 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계

• 전체의 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿈

• 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적화 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 없앨 수도 있다.

• 입력이 배열이거나 문자열이 경우 가능하다며 적절한 변환을 통해 메모이제이셔을 할 수 있도록 설계

• 메모이제이션 적용

• 그리고 Dynamic Programming 크게 Top-Down, Bottom-Up 방식 두 가지로 문제 풀이를 접근을 진행하게 된다.

• 하지만, 중복된 부분 문제을 찾는 과정과 중복된 부분 문제을 어떻게 메모이제이션을 적용하는지가 어렵기 때문에 많은 문제 풀이와 경험이 요구되는 것 같다.

Top-Down

---

• Top-Down은 큰 문제를 작은 문제로 나눠 재귀적 접근을 하는 방식이다.

• 문제를 풀어야 한다.

  • fibonacci(n)

• 문제를 작은 문제를 푼다

  • fibonacci(n - 1 )과 fibonacci(n - 2)로 문제를 나눈다

• 작은 문제를 푼다.

  • fibonacci(n - 1 )과 fibonacci(n - 2)를 호출해 문제를 나눈다

• 작은 문제를 풀었으니, 이제 문제를 푼다

  • fibonacci(n - 1)의 값과 fibonacci(n-2)의 값을 더해 문제를 푼다.

Bottom-Up

---

• Bottom-Up은 반대로 문제를 작은 문제부터 풀어 최종 문제까지 접근하는 접근 방식이다.

• 문제를 크기가 작은 문제부터 차례대로 푼다.

  • for(int = 2 ; i ≤n ; i++)

• 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다

  • for(int = 2 ; i ≤n ; i++)

• 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

  • d[i] = d[i - 1] + d[i - 2]

• 그러다보면, 언젠간 풀어야 하는 문제를 풀 수 있다.

  • d[n]]을 구하게 된다.

Dynamic Programming Example

---

코딩테스트 연습 - 카드 게임

문제 설명

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.

각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.`

왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.

제한 사항

• 한 더미에는 1장 이상 2,000장 이하의 카드가 있다.
• 각 카드에 적힌 정수는 1 이상 2,000 이하이다.

문제 풀이

---

• 위 문제는 문제의 조건에 따라 몇 가지 경우를 고려해 "최종 점수의 최대값"을 구하는 최적화 문제이다.
• 그렇다면 우선, 최적화 문제를 풀기 위해 모든 답을 만들어 본 후 그중에 최적해의 점수를 반환하는 완전 탐색 알고리즘 설계부터 하면 다음과 같다.

1. left[i] > right[i]인 경우 무조건 오른쪽 카드버리고 점수 획득
2. left[i] <= right[i]인 경우 왼쪽 카드만 버리는 경우와 왼쪽, 오른쪽 카드 모두 버리는 경우 존재. 따라서 두 가지 경우 중 가장 큰 점수를 반환하는 경우를 채택.

• 그리고 위 완전 탐색을 메모이제이션을 적용해 점화식을 설계하면 다음과 같다.

d[i][j] = left을 i만큼, right을 j만큼 버린고 획득한 점수의 최대값

• 즉 완전 탐색 알고리즘의 2번 부분을 메모이제이션을 통해 Overlapping Subproblem을 해결한 구조라고 보면 된다.

public class CardGame {

    private static int[][] dp;

    private static int sum = 0;

    public static int solution(int[] left, int[] right) {
        int ans = 0;
        dp = new int[left.length][right.length];

        for (int i = 0; i < left.length; i++) {
            Arrays.fill(dp[i], -1);
        }

        ans = searchMaxSum(left, right, 0, 0);
        return ans;
    }

    private static int searchMaxSum(int[] left, int[] right, int leftLoc, int rightLoc) {
        if (leftLoc == left.length || rightLoc == right.length) {
            return sum;
        }

        if (dp[leftLoc][rightLoc] != -1) {
            return dp[leftLoc][rightLoc];
        }

        if (left[leftLoc] > right[rightLoc]) {
            int currentSum = searchMaxSum(left, right, leftLoc, rightLoc+1) + right[rightLoc];
            dp[leftLoc][rightLoc] = currentSum;
            return currentSum;
        } else {
            int currentSum = Math.max(searchMaxSum(left, right, leftLoc + 1, rightLoc + 1), searchMaxSum(left, right, leftLoc+1, rightLoc));
            dp[leftLoc][rightLoc] = currentSum;
            return currentSum;
        }
    }
}

• 위 코드는 재귀함수 호출을 통해 구현한 방식이다. left[i] > right[i]인 경우에는 오른쪽 카드 버리고 점수를 획득한 후 최대값을 찾고, 그 외의 경우에는 왼쪽 카드만 버리는 경우, 왼쪽 오른쪽 카드 모두 버리는 경우를 모두 고려해 최대 값을 찾는 문제로 나눠서 구현한 내용이다. 그리고 반환된 최대값은 dp[leftLoc][rightLoc]라는 2차원 배열에 저장해 Memoization을 구현했다.