[알고리즘] DP - 예시 문제들

1. Fibbonacci 수 계산하기

2. 계단 오르는 경우의 수

 

3. 도미노 타일링

<점화식이 여러 작은 문제의 합으로 표현되는 경우>

-> 2 * N 크기의 벽을 2 * 1, 1 * 2 크기의 타일로 채울려고 하는 경우 

1) subproblem 

dp[i-1]

dp[i-2]

2) 점화식

dp[i] = dp[i-1] + dp[i-2]

3) dp 테이블 채우기 - tabulation

 

 

 

 

4. 최대합 계산하기

5. zig-zag 수열

 

6. LCS(Longest Common Subsequence) 계산하기

문제 정의

대표적인 DP 문제로 두 문자열 X, Y의 가장 긴 공통 부문자열을 찾는 문제임. 

 

활용

DNA 시퀀스가 서로 얼마나 가까운 유전자인지 LCS 길이를 통해 알 수 있다. -> 유전 공학에 쓰인다고 교수님께서 말씀해주셨다

 

어떻게 풀까? 

두 문자열이 주어지고 두 문자열의 공통 부문자열을 구해야한다. 

- X = A B C B D A B

- Y = B D C A B A 

 

1) 공통 부문자열을 구하기 위해서 먼저 해를 분석하여 부문제로 분할한다. 

LCS(Xi, Yj)를 구하는 것이 부문제가 됨. 

 

맨 끝의 두 문자가 다른 경우와 맨 끝의 두 문자가 같은 경우 두가지로 나눌 수 있다. 

if X7 != Y6:

LCS(X7, Y6)은 LCS(X7, Y5)나 LCS(X6, Y6) 중 더 긴 것이다. 

맨 끝의 두 문자가 다른 경우에는 둘 중 어느 것을 고른 게 최장 문자열일지 모르기 때문이다.

if X7 == Y6:

LCS(X7, Y6)은 LC(X6, Y5) + 1이다. 

두 문자가 같기 때문에 뭘 고르든 최장 문자열이기 때문이다. 

 

코드 구현

X = list(input())
Y = list(input())

def LCS(X, Y):
    n = len(X)
    m = len(Y)

    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[j-1] != Y[i-1]:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            else:
                dp[i][j] = dp[i-1][j-1] + 1

    print(dp[m][n])
    
LCS(X, Y)

 

7. 편집거리문제 (Edit distance problem)

문제 정의

문자열 X의 어떤 문자를 지우거나(delete) 새로운 문자를 삽입해서(insert) 다른 문자열 Y를 만들 수 있다. 따라서 편집 거리문제는 최소 횟수의 삽입 또는 삭제 연산으로 X를 Y로 변경할 수 있는지를 계산하는 문제이다.

 

어떻게 풀까?

X = HUMAN

Y = CHIMPANZEE

요 X가 Y로 바뀌는 것을 삽입, 삭제, 교체 연산으로 표현하기~

 

ex) HUMAN -> HMAN -> CHMAN -> CHIMAN -> CHMPAN -> CHIMPANZEE

 

삽입 연산 - Wins(z) = X 문자열에 문자 z를 삽입하는 비용

삭제 연산 - Wdel(z) = X 문자열에서 문자 z를 삭제하는 비용

교체 연산 - Wsub(z) = X 문자열에서 문자 ~를 z로 교체하는 비용

 

dp 테이블로 표현하면? 

dp[i][j] : Xi -> Yj의 최소 비용

dp[n][m] : Xn -> Ym의 최소 비용

dp[i][0] : Xi -> Y0의 최소 비용 - 모두 삭제 비용

dp[0][j] : X0 -> Yj의 최소 비용 - 모두 삽입 비용

이런 식으로 dp테이블을 나타낼 수 있다

 

dp테이블을 채우기 전 일단 문제를 쪼개야 한다. 

먼저 해를 분석하여 부문제로 분할한다! 

 

dp[i][j]의 값은 Xi -> Yj의 최소 비용인데

이를 구하기 위해서는 

1 - Wdel(Xi) + dp[i-1][j](Xi-1 -> Yj의 최소비용)

2 - dp[i][j-1](Xi -> Yj-1의 최소비용) + Wins(Yj)

3 - dp[i-1][j-1] + Wsub(Xi, Yj)

이렇게 분할해서 생각할 수 있고 

이 중 가장 작은 값이 dp[i][j]의 값이 된다. -> min(1, 2, 3)

 

이걸 for문을 돌려서 dp테이블을 채우고

이를 바탕으로 최종적으로 구하고 싶은 값을 구하면 됨! 

 

8. 괄호 만들기

문제 정의

행렬의 곱셈을 할 때 어떤 순서로 하느냐에 따라 기본 연산의 횟수가 크게 달라진다. 따라서 행렬의 곱셈을 하기 위해 기본 연산의 횟수가 최소가 되도록 괄호를 쳐서 순서를 정하는 것이 중요하다. 이 문제는 행렬의 곱셈이 최소 비용이 되도록 괄호를 치는 방법을 계산하는 것이 목적이다. 

 

어떻게 풀까?

이 문제를 풀기 위해서 해를 살펴보고 작은 부문제로 나누어 보자.

M1 * M2 * M3 * M4 이런 행렬의 곱셈이 있다면, 

괄호의 경우의 수는 다음과 같은 5가지 이다.

 

1 - M1 * ((M2 * M3) * M4)

2 - M1 * (M2 * (M3 * M4))

3 - ((M1 * M2) * (M3 * M4)) 

4 - ((M1 * M2) * M3) * M4

5 - (M1 * (M2 * M3)) * M4  

 

맨 마지막의 곱셈이 어느 것이냐에 따라 분류해볼 수 있는데, 

예를 들어 맨 마지막 곱셈이 첫번째 곱하기인 경우

M1을 계산하는 비용이 dp[1][1]이고,

(M2 * M3 * M4)을 계산하는 비용은 dp[2][4]이다. 

그리고 이 둘을 마지막에 곱하는 비용이 p1 * p2 * p5이다. 

이와 같이 맨 마지막 곱셈이 두번째 곱하기인 경우,

맨 마지막 곱셈이 세번째 곱하기인 경우도 마찬가지로 생각해 볼 수 있다. 

 

이렇게 곱셈을 앞에서부터 차례대로 보면서 

작은 부문제로 만들어 줬다. 

이를 일반화 해서 써보도록 하겠음

 

dp[i][j] = [mi * ... * mk] * [mk+1 *....*mj]

dp[i][j] = min(dp[i][k] + dp[k+1][j] + pi * pk+1 * pj+1들(i<= k < j))

위의 식을 좀 설명해 보자면,,,

k는 i부터 시작해서 j까지 커지는데, 

k와 k+1 사이에 곱하기를 하나씩 옮겨가는 것

곱하기를 기준으로 쪼개서 계산하여 필요한 비용의 경우의 수를 다 구하고

그들 중의 최소값을 취하는 것이다! 

쪼갰기 때문에 dp테이블에 모든 값들은 저장되어 있기 때문에 빠른 연산이 가능함

 

import math

def matrix_mult():
    for l in range(n-2, -1, -1):
    	for i in range(0, l+1):
            j = i + (n-1-l)
            C[i][j] = math.inf # math module에서 제공하는 매우 큰 정수
            for k in range(i, j):
                cost = C[i][k] + C[k+1][j] + P[i]*P[k+1]*P[j+1]
                if C[i][j] > cost:
                    C[i][j] = cost
    return C[0][n-1]

n = int(input()) # n = 행렬 갯수, M_0부터 행렬시작임을 주의!
matrix = [list(map(int, input().split())) for _ in range(n)]
P = [matrix[0][0]] + [x[1] for x in matrix] # M_i = p_i x p_{i+1}
C = [[0]*n for _ in range(n)] # 비용을 저장할 2차원 리스트 C 초기화

min_cost = matrix_mult()
print(min_cost)

모든 테스트 케이스 통과 되는지는 모르겠음,,

왜냐면 일단 코드트리에서는 안돌아가는데 

코드트리 테케가 좀 이상해서?

백준 돌려보는 중 -> 맞았당

 

9. LIS 최장 증가 부수열

문제 정의

가장 긴 증가 부수열을 찾는 문제이다. 지그재그 수열처럼 앞의 수열들을 dp로 저장해 가장 긴 증가 부수열을 찾을 수 있다. 

예를 들어 A = [2, 8, 5, 10, 18, 13, 20, 4] 인 경우에 2, 5, 10, 18, 20과 8, 10, 13 모두 증가 부수열이지만 앞의 부수열의 길이가 더 길기 때문에 앞의 것이 최장 증가 부수열이다. 

 

어떻게 풀까?

앞에서부터 차례로 살펴보면서 만약 j < i 일 때 A[j] < A[i] 이면 LIS[i] = max(LIS[i], LIS[j]+1) -> 만약 LIS[i]보다 LIS[j]+1가 크면 LIS[i]는 LIS[j]+1

 

코드 구현

n = int(input())
A = list(map(int, input().split()))

def make_LIS(n, A):
    LIS = [0 for _ in range(n)]
    LIS[0] = 1
    for i in range(1, n):
        LIS[i] = 1
        for j in range(i):
            if A[j] < A[i]:
                LIS[i] = max(LIS[i], LIS[j]+1)
    return max(LIS)

print(make_LIS(n, A))

 

코드트리 문제 -최대 점프 횟수