[코테스터디] 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍(동적 계획법)

보통 알고리즘 문제를 풀 때 시간과 메모리를 절약하면서 효율적인 알고리즘을 작성한다.

다만, 어떤 문제는 메모리 공간을 좀 사용해서 푸는 문제가 있는데 그 문제가 다이나믹 프로그래밍(DP) 문제이다. 다이나믹 프로그래밍 문제는 한번에 해결하는 문제가 아니라 조금씩 점차적으로 풀어가는 문제이므로 점화식을 생각하면서 풀어야 한다.다이나믹 프로그래밍 문제를 푸는 유형에는 탑다운(Top-down)과 보텀업(Bottom-up)이 있다. 개인적으로 선호하는 방식을 택하면서 풀면 된다. 물론, 연습할 때 두가지를 이용해 풀어보면 좋을 것이다.

• 탑다운, 하향식(Top-down)
  • 재귀 함수를 이용해 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다.
  • 메모이제이션을 이용해 재귀함수를 통해 발생하는 동일 함수 반복을 줄여 계산한 적 있는 문제는 그대로 반환한다.(한 번 푼 문제는 다시 구하지 않는 방식이다. 다만, 구한 값을 다시 사용한다.)
  • 재귀 함수의 스택이 한정되어 있으므로 `sys.setrecursionlimit()` 메소드를 호출하여 함수 깊이 에러를 방지하면 좋다. 
• 보텀업, 상향식(Bottom-up)
  • 작은 문제부터 차근차근 답을 도출하는 방식이다.
  • DP 테이블이라는 결과용 리스트를 활용해 계산된 결과를 저장하는 방식이다.

보통 완전 탐색 알고리즘으로 접근했을 때 시간이 오래 걸릴 것 같으면 다이나믹 프로그랭을 적용할 수 있는지 부분 문제들의 중복 여부를 확인해보자.

💡 점화식
점화식은 인접한 항들 사이의 관계식을 의미한다. 즉, 현재의 항을 이전의 항에 대한 식으로 표현할 수 있다.  앞에서 구했던 식들의 조합으로 문제를 풀어야 한다.

 

---

2차원 배열 문제

대표적인 문제로 피보나치 수열 문제가 있으나 그래도 난이도 있는 문제를 풀어보려고 한다.

해당 문제는 평범한 배낭 - 백준↗ 문제이다. 

 

준서가 여행에 필요하다고 생각하는 물건 `N`개가 주어졌을 때, 각 물건의 무게(`W`)와 가치(`V`)가 주어진다. 최대 `K`무게 만큼만 배낭에 넣을 수 있다고 한다. 그렇다면 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 출력해야한다.

 

입력 조건

4 7
6 13
4 8
3 6
5 12

 

출력 조건

14

 

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

 

해설

먼저 물품의 개수와 최대 무게를 입력받는다.

n, k = map(int, input().split())

 

최대 가치를 구하기 위해 2차원 배열을 이용하여 DP 테이블에 메모하면서 가치를 갱신하려고 한다.

dp = [[0] * (k + 1) for _ in range(n + 1)]

 

물품의 개수만큼 물품들의 무게(W)와 가치(V)를 입력 받고 해당 물품의 무게와 이전에 작성된 무게(`dp[i-1][j-w]`)에 현재 가치(`v`)를 더한 값이랑 이전 가치(`dp[i-1][j]`)를 비교해 최대 값을 담는다. 

for i in range(1, n+1):
	w, v = map(int, input().split())
    for j in range(1, k+1):
    	if j < w: # 현재 무게 이전 값
        	dp[i][j] = dp[i-1][j]
        else:
        	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) # 둘 중 최대 가치

파란색 동그라미 표시들과 비교해 dp[2][4]에 담는다.

 

해당 테이블을 다 완성하게 되면 결국엔 최대 값은 14가 되는 것이다.

print(dp[n][k])

 

가장 기본적으로 다루고 꼭 알야할 문제이니 기억해두자.

최장 증가 수열(LIS)

가장 긴 증가하는 부분 수열 문제(LIS)는 다이나믹 프로그래밍의 DP 테이블을 활용해 풀 수 있는 문제이다. 최장 증가 수열은 N개의 원소가 있는 배열에서 일부 원소를 골라내 만든 수열로 오름차순을 유지하는 부분 수열 중 가장 긴 수열을 찾는 것이다.

우리는 DP 테이블을 활용하여 DP 테이블에서 마지막 원소의 값을 부분 수열의 최대 길이로 정의한다.

 

무조건 정답이 [2,3,5,6,7]이 되는 것이 아니라 [1,3,5,6,7]도 될 수 있다.

 

예를 들어, 다음 병사 배치하기(백준) 문제를 보자.

문제

입력조건

7
15 11 4 8 5 2 4

출력 조건

2

 

해설

해당 문제는 병사의 전투력에 따라 내림차 순으로 배치해야한다. 즉, 가장 길게 감소하는 부분 수열의 길이를 구해야한다. 

그럼 다음과 같이 입력 순서를 뒤집은 후, 증가하는 수열 점화식을 사용하면 된다.

 

n = int(input())
lst = list(map(int, input().split()))
lst.reverse() # 감소하는 가장 긴 수열을 위해 뒤집기

dp = [1] * n

# LIS 알고리즘 수행
for i in range(1, n):
  for j in range(0, i):
    if lst[j] < lst[i]:
      dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp)) # 열외

최장 공통 부분 수열(LCS)

LCS는 최장 공통 부분수열(Longest Common Subsequence; Substring)을 말한다. 

최장 공통 부분수열과 최장 공통 문자열은 비슷하나 차이가 있다. 부분수열은 문자 사이를 건너뛰어 공통이면서 가장 기분 부분을 찾으면 되지만 문자열은 한번에 이어진 경우에만 가능하다.

 

그럼 어떻게 찾을 수 있을까?

먼저, 2차원 배열을 생성해 두 문자열을 비교하면서 문자가 같은 경우와 문자가 다른 경우에 값을 표시하면 된다. 

1. 만약, 두 문자가 동일하다면 대각선에서 값을 찾아 +1을 한다. (지금까지의 공통 부분 수열에 +1)
2. 만약, 두 문자가 다르다면 0을 표시한다. 만약 길이를 구한다고 가정하면, 왼쪽과 위쪽 중 큰 값을 넣는다.

a, b = input(), input()
LCS = [[0]* (len(b)+1) for _ in range(len(a)+1)] # 초기 테이블

for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1]: # 문자가 같은 경우
            LCS[i][j] = LCS[i - 1][j - 1] + 1
        else: # 그렇지 않은 경우
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

 

최대 공통 부분 수열은 현재 문자가 달라도 계속 유지되기 때문에 이전에 과정을 가져온다.

 

길이가 아닌 문자를 탐색하는 경우, 다음과 같이 탐색으로 문자열을 반환한다.

• 가장 오른쪽 하단의 문자부터 좌, 상의 글자들이랑 맞는지 확인
• 다르다면, 좌측 대각선으로 탐색

 

 

그림으로 알아보는 LCS 알고리즘 - emplam27.log↗

📝 풀어보기 좋은 문제들

• 프로그래머스 - 정수 삼각형
• 퇴사 - 백준
• 가장 긴 증가하는 부분 수열 - 백준
• 가장높은탑쌓기 - 백준