DP 완전 정복

1. 배경

이분 탐색 다음으로 정리할 알고리즘으로 DP를 택한 것은 이분 탐색과 완전히 대척점이 되는 점에서 어렵게 느껴졌기 때문이다. 이분 탐색의 경우 구현 자체는 쉽지만 문제 접근을 이분 탐색으로 해야된다는 것을 깨닫는 것이 어렵다면 DP는 뭔가 딱 봐도 DP로 구현해야될 것 같은데 실제 코드로 구현하는 것이 어렵기 때문이다.

 

따라서 이분 탐색에서 접근 방법 위주로 글을 썼다면 이번엔 구현을 어떻게 해야 하는지 위주로 글을 쓰고자 한다.

 

2. DP란?

부분 반복 문제과 최적 부분 구조를 가지는 알고리즘을 메모제이션을 통해 더 빠르게 해결하는 방법을 말한다.

정의가 어렵지 않고 피보나치의 유명한 예시 덕분에 많은 사람들이 정의를 어려워할 것이라 생각하지는 않는다.

핵심적인 개념을 짚고 넘어가자면

 

"부분 반복 문제"

"최적 부분 구조"

"메모제이션"

 

이 세가지라 할 수 있다.

부분 반복 문제 : 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있을 때를 말한다. 예를 들어 피보나치의 경우 fib(n)을 구하기 위해서는 fib(n-1), fib(n-2), fib(n-3)... 이런 부분 문제로 쪼개질 수 있다.

최적 부분 구조 : 작은 부분 문제에서 구한 최적의 답으로 큰 문제의 최적의 답을 구할 수 있다. 마찬가지로 피보나치의 예를 들어 보자면 fib(n) = fib(n-1) + fib(n-2) 에서 fib(n)이 최적의 답이 되려면 fib(n-1)과 fib(n-2)이 최적의 답이어야 한다.
여기서 핵심은 fib(n)의 값은 어느때나 고정된 값을 가진다는 점이다.

메모제이션 : 부분 반복 문제를 가졌을 때 동일한 계산을 반복하게 된다면 이전에 계산한 값을 메모리에 저장함으로써 반복 수행을 제거하는 기술이다. DP의 핵심 개념이다.

 

3. DP 접근법

DP를 적용하려면 가장 먼저 확인해야할 것이 있다. 바로 "부분 문제 반복이 적용되는지" 이다.

즉 큰 문제가 여러 개의 부분 문제로 쪼개질 수 있는지를 확인해야한다. 이를 위해 점화식 또는 재귀 과정을 정의한다. 재귀 과정이므로 종료 조건을 세밀하게 세워야하는 것은 필수이다.

그리고 해당 문제가 같은 하위 문제를 반복해서 계산하는지 분석한다. 하위 문제를 많이 반복한다면 DP가 적합하다.

 

4. 실전 예제

앞서 말한 것처럼 DP를 통해 풀어야겠다고 떠올리는 것은 어렵지 않다. 하위 문제 반복과 그 반복이 지나치게 커지는 것은 직관적으로 알아차리기 쉽기 때문이다.

하지만 실전 예제에서 어떻게 재귀식을 세우고 메모제이션을 할 지 코드를 짜는 것이 결국 DP 핵심이다. 그러므로 이번 글에서는 문제를 다양하게 살펴보며 코드를 통해 설명하고자 한다.

4.1 N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

위 문제는 숫자 N을 최소한으로 이용하여 사칙연산을 통해 주어진 number를 만들어야 하는 문제이다.

이 문제가 DP라는 것은 쉽게 알아차릴 수 있다. 숫자를 i개 사용하여 계산한 연산의 결과는 앞서 연산한 i-1, i-2, i-3... 개를 사용하여 계산한 값들의 조합이기 때문이다.

예를 들어 숫자 N이 3번 사용된다면

{N1 N1 N1 , N1 N2, N2 N1}의 조합이 될 것이다. (나눗셈, 뺄셈도 있으므로 순서도 고려해야 한다.)

즉 Nn 이라면 (n-1 1),  (n-2 2),  (n-3 3), .... ,(1 n-1) 로 조합된 결과일 것이다.

 

그렇다면 메모제이션은 어디 적용되어야 할까?

Nn을 구할 때, Nn-1, Nn-2, Nn-3... 의 경우 미리 구해놓고 메모리에 저장해놓는다면 다시 연산할 필요 없이 활용할 수 있다.

이를 통해 코드로 구현해보자.

def solution(N, number):
    S = [{N}]
    for i in range(2, 9):
        lst = [int(str(N)*i)]
        for X_i in range(0, int(i / 2)):
            for x in S[X_i]:
                for y in S[i - X_i - 2]:
                    lst.append(x + y)
                    lst.append(x - y)
                    lst.append(y - x)
                    lst.append(x * y)
                    if x != 0: lst.append(y // x)
                    if y != 0: lst.append(x // y)
        if number in set(lst):
            return i
        S.append(lst)
    return -1

4.2 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

DFS가 바로 떠오르는 문제이다. 물론 DP로 더 효율적으로 접근할 수 있다.

삼각형을 내려가는 규칙은 왼쪽과 오른쪽으로만 내려갈 수 있다는 것이다. 그럼 반대로 아래 숫자 입장에서 생각해보면 왼쪽 위와 오른쪽 대각선 위 중에서 더 큰 합계를 가졌던 경로의 값을 가져오면 그 지점까지 오는 가장 큰 값을 구할 수 있다.

이를 통해 위에서부터 메모제이션을 해나가면서 최댓값을 구할 수 있다.

점화식을 세우자면

dp[i][j] = MAX(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]

이다.

 

코드로 구현해보자면

def solution(triangle):
    dp = []
    for t in range(1, len(triangle)):
        for i in range(t+1):
            if i == 0:
                triangle[t][0] += triangle[t-1][0]
            elif i == t:
                triangle[t][-1] += triangle[t-1][-1]
            else:
                triangle[t][i] += max(triangle[t-1][i-1], triangle[t-1][i])
    return max(triangle[-1])

이다.

 

지금까지는 비교적 메모제이션 구현이 어렵지 않은 문제였다.

다음 문제부터는 level4 이상의 문제를 다뤄보려고 한다.

 

4.3 도둑질

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

 

이 문제의 경우 i번째 집을 턴다고 가정했을 때

1.  i-1, i+1의 인접한 집을 털 경우 경보가 울린다.
2. 마을이 원형이기 때문에 첫번째 집과 마지막 집 또한 이웃이다.

를 고려해야 한다.

 

dp인 것을 떠올리기도 사실 쉽지 않은 문제이다. 하지만 작은 문제로 쪼갤 수 있음을 깨달으면 금방 DP로 발전할 수 있는데 이럴 땐 1, 2, 3...i 까지 발전시켜보는 것이 도움이 된다.

 

집이 하나라면? 그 집을 터는 것이 최댓값이다.

집이 둘 일 경우? 인접한 집을 털지 못하므로 두 집 중 money가 큰 것이다.

집이 셋 이상일 경우? 현재 i집 money + i-2번째 집 혹은 i-1집 중 더 큰 값을 가져오면 된다.

 

점화식으로 표현하면

dp[i] = max(dp[i-1], money[i] + dp[i-1])

로 표현할 수 있다.

 

여기서 위에서 언급한 집이 원형인 것을 고려해주면

1) 첫번째 집을 무조건 털고 마지막 집을 털지 않거나

2) 마지막 집을 무조건 털고 첫번째 집은 털지 않는 경우

나눠서 구현해준다.

def solution(money):
    dp1 = [0] * len(money)
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1])

    for i in range(2, len(money)-1): # 첫 집을 무조건 터는 경우
        dp1[i] = max(dp1[i-1], money[i]+dp1[i-2])

    dp2 = [0] * len(money)
    dp2[0] = 0
    dp2[1] = money[1]

    for i in range(2, len(money)): # 마지막 집을 무조건 터는 경우
        dp2[i] = max(dp2[i-1], money[i]+dp2[i-2])

    return max(max(dp1), max(dp2)) # 두 경우 중 최대

 

다음과 같다.

 

4.4 사칙연산

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

위에서 살펴본 N으로 표현과 문제가 유사하다.

즉 N개의 숫자로 이루어진 연산이라면

 

(1, N-1) (2, N-2) (3, N-3)...

(각 숫자는 순서를 말함.)

의 조합으로 이루어짐을 알 수 있다.

 

그렇다면 DP[i][j]의 값을 i 번째 피연산자부터 j번째 피연산자까지의 최댓값으로 정의할 수 있다.

 

다만 연산자가 주어진 대로만 계산이 진행된다는 점에서 점화식을 세우기 쉽지 않다.

우리에게 주어진 연산자는 +와 - 이다. 우린 최댓값을 구해야하는데 +와 - 모두 주어지므로 가장 큰 값과 가장 작은 값 모두 필요하다. 따라서 위에서 확장하여

MAX_DP[i][j] : i번째 피연산자부터 j번째 피연산자까지 최댓값
MIN_DP[i][j] : i번째 피연산자부터 j번째 피연산자까지 최솟값

으로 재정의할 수 있다.

 

그리고 MAX_DP의 경우

덧셈 : max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][new] + max_dp[new+1][j])
뺄셈 : max_dp[i][j] = Math.max(max_dp[i][j], max_dp[i][new] - min_dp[new+1][j])

MIN_DP의 경우

덧셈 : min_dp[i][j] = Math.max(min_dp[i][j], max_dp[i][new] + min_dp[new+1][j])
뺄셈 : min_dp[i][j] = Math.max(min_dp[i][j], max_dp[i][new] - max_dp[new+1][j])

이다.

각각의 DP 배열을 -INF와 INF로 초기화해준 뒤

점화식을 그대로 구현해주면 해결된다.

 

이 문제 참고 자료 :  https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0

 

이 문제까지 해결한다면 코딩테스트에 출제되는 DP 문제는 웬만하면 풀 수 있을 것이라 생각한다!