[Python] 동적 계획법

# 11-1. 동적 계획법 알아보기

동적 계획법(dynamic programming)이란?

• 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제를 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

DP의 핵심 이론

• 원리
  • 큰 문제들을 작은 문제로 나눌 수 있어야 한다.
  • 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
  • 메모제이션(memozation) 기법 : 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
  • DP는 top-down 혹은 bottom-up 방식으로 구현할 수 있다.
• 예시(피보나치 수열) : D[N] = D[N-1] + D[N-2]
• https://www.acmicpc.net/problem/2747
• top-down 구현 방식은 주로 재귀 함수 형태로 구현한다. 코드의 가독성이 좋고 이해하기 편하다.

import sys
input = sys.stdin.readline

N = int(input())
D = [-1]*(N+1)
D[0] = 0
D[1] = 1

def fibo(n):
    if D[n]!=-1: # 기존에 계산한 적이 있는 부분의 문제는 계산하지 않고 리턴
        return D[n]
    # 메모리제이션
    D[n] = fibo(n-2)+fibo(n-1)
    return D[n]

fibo(N)
print(D[N])

• bottom-up 구현 방식은 주로 반복문의 형태로 구현한다. 좀 더 안전한 방식(재귀의 깊이를 고려할 필요x)

import sys
input = sys.stdin.readline

N = int(input())
D = [-1]*(N+1)
D[0] = 0
D[1] = 1

for i in range(2, N+1):
    D[i] = D[i-2] + D[i-1] # 반복문을 사용해서 아래부터 값을 채워나가는 방식

print(D[N])

 

 

https://www.acmicpc.net/problem/1463

import sys
input = sys.stdin.readline

N = int(input())
D = [0]*(N+1)
D[1] = 0

for i in range(2, N+1):
    D[i] = D[i-1] + 1
    if i%2==0:
        D[i] = min(D[i], D[i//2]+1)
    if i%3==0:
        D[i] = min(D[i],D[i//3]+1)

print(D[N])

• D[i] = i에서 1로 만드는 데 걸리는 최소 연산 횟수
• 점화식을 구한다. 2 혹은 3으로 나누는 연산이 가능한 경우 D[i-1]+1과 D[i/3]+1 중 최솟값으로 채운다.

 

https://www.acmicpc.net/problem/14501

import sys
input = sys.stdin.readline

N = int(input())
D = [0]*(N+2) # 오늘부터 퇴사일까지 벌 수 있는 최대 수입
T = [0]*(N+1) # 상담에 필요한 일수
P = [0]*(N+1) # 상담 완료 시 수입

for i in range(1, N+1):
    T[i], P[i] = map(int, input().split())

for i in range(N, 0, -1):
    if i+T[i] > N+1:
        D[i] = D[i+1]
    else:
        D[i] = max(D[i+1], P[i]+D[i+T[i]])

print(D[1])

• D[i] = i번째 날부터 퇴사날까지 벌 수 있는 최대 수입
• 오늘 시작되는 상담을 했을 때 퇴사일까지 끝나지 않는 경우 D[i] = D[i+1]
• 오늘 시작되는 상담을 했을 때 퇴사일 안에 끝나는 경우 D[i] = MAX(D[i+1], D[i+T[i]] + P[i]
• 상담의 뒤에서부터 접근한다!

 

https://www.acmicpc.net/problem/2193

import sys
input = sys.stdin.readline

N = int(input())
D = [[0 for j in range(2)] for i in range(N+1)]
D[1][1] = 1 # 1자리 이친수는 1 한가지만 존재
D[1][0] = 0

for i in range(2, N+1):
    D[i][0] = D[i-1][1] + D[i-1][0]
    D[i][1] = D[i-1][0]

print(D[N][0] + D[N][1])

• D[i][0] = i 길이에서 끝이 0으로 끝나는 이친수의 개수, D[i][1] = i길이에서 끝이 1로 끝나는 이친수의 개수
• 이전 단계에서 0으로 끝나는 경우에만 1을 붙인다.

 

https://www.acmicpc.net/problem/11726

import sys
input = sys.stdin.readline
mod = 10007

N = int(input())
D=[0]*1001
D[1] = 1 # 길이가 2x1일 때 타일의 경우의 수
D[2] = 2 # 길이가 2x2일 때 타일의 경우의 수

for i in range(3, N+1):
    D[i] = (D[i-1]+D[i-2])%mod # 점화식

print(D[N])

• 경우의 수는 현재 N번째 타일을 채울 때, N-1 타일까지 채워져 있거나 N-2 타일까지 채워야 하는 경우로 나눌 수 있다.
• N-1인 경우 세로로 타일 1개를 채우고, N-2인 경우 가로로 타일 2개를 채운다.(세로로 2개는 N-1의 경우와 같음)
• D[N] = D[N-1] + D[N-2] = 길이 N으로 만들 수 있는 타일의 경우의 수
• DP 테이블을 채울 때마다 %연산을 수행한다.

 

https://www.acmicpc.net/problem/10844

import sys
input = sys.stdin.readline
mod = 1000000000

N = int(input())
D=[[0 for j in range(11)] for i in range(N+1)]
# D[i][j] = 길이가 i일때 높이 j로 끝나는 모든 경우의 수

for i in range(1, 10):
    D[1][i] = 1 # 길이가 1일 때 만드는 높이 H로 끝나는 계단 수의 모든 경우의 수는 1

for i in range(2, N+1):
    D[i][0] = D[i-1][1] # N에서 높이가 0이면 N-1에서는 높이가 1이여야 계단 수가 가능
    D[i][9] = D[i-1][8] # N에서 높이가 9이면 N-1에서는 높이가 8이여야 계단 수가 가능
    for j in range(1,9):
        # 높이가 1~8이면 N-1에서 자신보다 한 단계 위 혹은 한 단계 아래 높이에서 올 수 있음
        D[i][j] = (D[i-1][j-1] + D[i-1][j+1])%mod

sum = 0

for i in range(10):
    sum = (sum+D[N][i])%mod # 정답값을 더할 때도 %연산 수행

print(sum)

 

• D[N][H] = 길이가 N인 계단에서 H 높이로 종료되는 계단 수를 만들 수 있는 경우의 수
• 즉 D[N][5]에서, N-1에 올 수 있는 수는 4와 6이다.
• D[N][0]~D[N][9]의 모든 값을 더하면 모든 경우의 수를 구할 수 있다.

 

https://www.acmicpc.net/problem/13398

import sys
input = sys.stdin.readline
mod = 1000000000

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

# 오른쪽으로 index를 포함한 최대 연속 합 구하기
L = [0]*N
L[0] = A[0]
result = L[0]

for i in range(1, N):
    L[i] = max(A[i],L[i-1]+A[i])
    result = max(result, L[i]) # 제거하지 않았을 때는 기본 최댓값으로 저장

# 왼쪽으로 index를 포함한 최대 연속 합 구하기
R = [0]*N
R[N-1] = A[N-1]

for i in range(N-2, -1,-1):
    R[i] = max(A[i], R[i+1]+A[i])

# L[i-1] + R[i-1] 2개의 구간 합 리스트를 더하면 i번 째 값을 제거한 효과를 얻음
for i in range(1, N-1):
    temp = L[i-1]+R[i+1]
    result = max(result, temp)

print(result)

• D[N] = 0부터 N까지의 길이에서 N을 포함하며 연속으로 수를 선택하여 구할 수 있는 최대 합
• 1개의 수를 삭제할 수 있으므로, 왼쪽과 오른쪽 점화식을 구한다. L[N-1]+R[N+1] 은 N을 1개 제거한 최댓값을 구하는 효과가 있다.

 

 

https://www.acmicpc.net/problem/9252

• LCS 문제!
• 문자열 비교 문제는 이 문제와 비슷한게 많으므로 꼼꼼하게 숙지할 것.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

A = list(input())
A.pop() # \n문자열 제거
B = list(input())
B.pop() # \n 문자열 제거
DP = [[0 for j in range(len(B)+1)] for i in range(len(A)+1)]
Path = []

for i in range(1, len(A)+1):
    for j in range(1, len(B)+1):
        if A[i-1]==B[j-1]:
            # 같은 문자열일 때 왼쪽 대각선 값+1
            DP[i][j] = DP[i-1][j-1]+1
        else:
            # 다르면 왼쪽과 위의 값 중 큰 수
            DP[i][j] = max(DP[i-1][j], DP[i][j-1])

print(DP[len(A)][len(B)])

# LCS 구현 함수
def getText(r,c):
    if r==0 or c==0:
        return
    if A[r-1]==B[c-1]: # 같으면 LCS에 기록하고 왼쪽 위로 이동
        Path.append(A[r-1])
        getText(r-1, c-1)
    else: # 다르면 왼쪽과 위의 값 중 큰 수로 이동
        if DP[r-1][c]>DP[r][c-1]:
            getText(r-1,c)
        else:
            getText(r,c-1)

getText(len(A),len(B))

for i in range(len(Path)-1,-1,-1):
    print(Path.pop(i), end='')
print()

• 각 문자열을 축으로 하는 2차원 리스트를 생성한다.
• 테이블에 저장되는 값은 각 위치 인덱스를 마지막 문자로 하는 두 문자열의 LCS의 길이이다.
• LCS 점화식을 이용해 값을 채운다. 특정 자리가 가리키는행과 열의 문자열 값을 비교한다.
  • 값이 같으면 테이블의 대각선 왼쪽 위의 값에 1을 더한 값을 저장한다. DP[i][j]=DP[i-1][j-1]+1
  • 값이 다르면 테이블 왼쪽과 위쪽 값 중 큰 값을 선택해 저장한다. DP[i][j] = Max(DP[i-1][j], DP[i][j-1])
• LCS를 출력한다. 마지막부터 탐색을 수행하고 해당 자리에 있는 문자열 값을 비교해 값이 같으면 LCS(Path)에 기록하고 왼쪽 대각선으로 이동한다. 비교한 값이 다르면 테이블의 위쪽과 왼쪽 중 큰 값으로 이동한다.

 

https://www.acmicpc.net/problem/1915

import sys
input = sys.stdin.readline

D = [[0 for j in range(1001)] for i in range(1001)]
N, M = map(int, input().split())
max = 0

for i in range(0, N):
    numbers = list(input())
    for j in range(0, M):
        D[i][j] = int(numbers[j])
        if D[i][j] == 1 and j>0 and i >0:
            D[i][j] = min(D[i-1][j-1], D[i-1][j], D[i][j-1])+D[i][j] # 점화식
        if max<D[i][j]:
            max = D[i][j]

print(max*max)

• 가장 큰 정사각형의 한 변의 길이를 구한다.
• D[i][j] = i,j의 위치를 오른쪽 아래 꼭짓점으로 정하고, 해당 자리에서 그릴 수 있는 가장 큰 정사각형의 변의 길이
• 즉, 현재 위치에서 위, 왼쪽, 대각선 왼쪽 위에 있는 값 중 가장 작은 값에 1을 더한 값으로 변경한다. 원래 값이 0인 경우에는 그대로 둔다.

 

https://www.acmicpc.net/problem/1328

import sys
input = sys.stdin.readline
mod = 1000000007

N,L,R= map(int, input().split())
D = [[[0 for k in range(101)] for j in range(101)] for i in range(101)]
D[1][1][1] = 1 # 빌딩이 1개이면 놓을 수 있는 경우의 수는 1개

for i in range(2, N+1):
    for j in range(1, L+1):
        for k in range(1, R+1):
            D[i][j][k] = (D[i-1][j][k]*(i-2) + (D[i-1][j][k-1] + D[i-1][j-1][k]))%mod

print(D[N][L][R])

• D[N][L][R] = N개의 빌딩이 있고 왼쪽에서 L개, 오른쪽에서 R개가 보일 떄 가능한 경우의 수
• 가장 작은 빌딩을 N번째로 배치할 때 왼쪽/오른쪽/가운데로 나뉜다.
  • 왼쪽의 경우 왼쪽에서 보는 빌딩 증가, 오른쪽의 경우 오른쪽에서 보는 빌딩 증가, 가운데는 증가 X
• 즉 D[N-1]개의 빌딩에서 왼쪽에 빌딩을 추가할 때 이전 경우의 수는 D[N-1][L-1][R]이다. 
• 오른쪽에 추가하는 경우 D[N-1][L][R-1]이다.
• 가운데의 경우 증가 수는 없지만, N-2개에 위치할 수 있으므로 D[N-1][L][R]*(N-2)
• 위 3가지 경우의 수를 모두 더하면 점화식이 나온다.

 

https://www.acmicpc.net/problem/2342

import sys
input = sys.stdin.readline
# dp[N][L][R] = N개 수열을 수행했고, 왼쪽이 L 오른쪽이 R에 있을 때 최소 누적
# 충분히 큰 수로 초기화
dp = [[[sys.maxsize for k in range(5)] for j in range(5)] for i in range(100001)]
# 한 발을 이동할 때 드는 힘을 미리 저장하기(mp[1][2] -> 1에서 2로 이동할 때 드는 힘)
mp = [[0, 2, 2, 2, 2],
      [2, 1, 3, 4, 3],
      [2, 3, 1, 3, 4],
      [2, 4, 3, 1, 3],
      [2, 3, 4, 3, 1]]
s = 1
dp[0][0][0] = 0

inputList = list(map(int, input().split()))
index = 0

while inputList[index]!=0:
    n = inputList[index]
    for i in range(5):
        if n==i: # 두 발이 같은 자리에 있을 수 없음
            continue
        for j in range(5):
            # 오른발을 옮겨 현재 모습이 됐을 때 최소 힘 저장
            dp[s][i][n] = min(dp[s-1][i][j] + mp[j][n], dp[s][i][n])

    for j in range(5):
        if n==j: # 두 발이 같은 자리에 있을 수 없음
            continue
        for i in range(5):
            # 왼발을 옮겨 현재 모습이 됐을 때 최소 힘 저장
            dp[s][n][j] = min(dp[s-1][i][j] + mp[i][n], dp[s][n][j])
    s+=1
    index+=1

s-=1 # 마지막 이동 횟수로 index 조정
result = sys.maxsize

for i in range(5):
    for j in range(5):
        result = min(result, dp[s][i][j]) # 모두 수행한 후 최솟값 찾기

print(result)

• 수열의 최대 길이가 10만 이므로 모든 경우의 수를 점화식으로 표현해 구현한다.
• D[N][L][R] = N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 힘
• 예를 들어, 직전에 오른 다리가 2의 자리에 있다가 현재 R 자리로 이동했다면 D[N][L][R]의 최솟값 후보 중 하나로 D[N-1][L][2] + (2 -> R로 이동한 힘)이 될 수 있다.
• 즉 오른발의 경우 D[N][L][R] = MIN(D[N-1][L][i] + mp[i][R])
• 왼발은 D[N][L][R] = MIN(D[N-1][i][R] + mp[i][L])

 

https://www.acmicpc.net/problem/11049

import sys
input = sys.stdin.readline

N = int(input())
M = []
D = [[-1 for j in range(N+1)] for i in range(N+1)]

M.append((0,0))

for i in range(N):
    x,y = map(int, input().split())
    M.append((x,y))

def execute(s,e): # 탑-다운 방식 점화식 함수
    result = sys.maxsize
    if D[s][e] != -1: # 이미 계산한 부분은 다시 계산하지 않음(메모리제이션)
        return D[s][e]
    if s==e: # 행렬 1개의 곱셈 연산
        result = 0
    if s+1==e: # 행렬 2개의 곱셈 연산
        return M[s][0]*M[s][1]*M[e][1]
    for i in range(s,e): # 행렬 3개 이상일 경우 곱셈 연산 -> 재귀 형태로 계산
        result = min(result, M[s][0]*M[i][1]*M[e][1] + execute(s,i)+execute(i+1, e))
    D[s][e] = result
    return D[s][e]

print(execute(1, N))

• D[i][j] = i~j 구간의 행렬을 합치는 데 드는 최소 연산 횟수
• 즉 N번째 행렬을 합칠 때, D[1][N-1], D[N][N]값을 알고 있으므로 D[1][N-1]+D[N][N] +a (1개의 행렬로 합치는 데 드는 횟수)가 된다. 
• a는 두 행렬을 합치는데 드는 값으로 1번째 행렬의 row 개수, N번째 행렬의 row 개수, column 개수를 곱한다.
  • 2x3, 3x6 행렬을 합치는 경우 a = 2x3x6 = 36
• 구하려는 영역의 행렬 개수가 3개 이상일 때는 이 영역을 재귀 형태로 쪼개면서 계산한다.
• Python 시간초과나서 PyPy로 제출함.

 

https://www.acmicpc.net/problem/2098

• 중요한 TSP 문제! DFS, DP, 비트연산까지 나오는데 이게 플레가 아니라니..
• 음 책 그대로 썼는데 실수를 했는지 틀리게 나온다...비슷한 다른 풀이 참고함.

import sys
N = int(input())
world = []
for _ in range(N):
    world.append(list(map(int, sys.stdin.readline().split())))

dp = {}


def DFS(now, visited):
    # 모든 도시를 방문한 경우
    if visited == (1 << N) - 1:
        # 다시 출발 도시로 갈 수 있는 경우 출발 도시까지의 비용 반환
        if world[now][0]:
            return world[now][0]
        else:
            # 갈 수 없는 경우 무한대 반환 (이 경로가 최소비용으로 채택되지 않게)
            return int(1e9)

    # 이전에 계산된 경우 결과 반환
    if (now, visited) in dp:
        return dp[(now, visited)] # now까지 방문한 최소 비용

    min_cost = int(1e9)
    for next in range(1, N):
        # 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
        if world[now][next] == 0 or visited & (1 << next):
            continue
        cost = DFS(next, visited | (1 << next)) + world[now][next]
        min_cost = min(cost, min_cost)

    dp[(now, visited)] = min_cost  # 현재도시까지 방문한 경우 중에서 최소 비용이 드는 루트의 비용 저장
    return min_cost  # 현재도시까지 방문하는 비용 리턴


print(DFS(0, 1))  # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리

• D[c][v] = 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v일 떄 앞으로 남은 모든 도시를 경유하는 데 필요한 최소 비용
• v에 현재까지 방문한 리스트를 저장하기 위해 이진수를 이용한다. 
  • 예를 들어, 4번, 1번을 방문한 경우 이진수로 1001로 표현하고, D[i][9]로 리스트를 표현한다.
• D[c][v] = MIN(D[c][v], D[i][v | (1<<i)] +W[c][i]) -> W[c][i]는 c에서 i로 가기 위한 비용
• << : 비트 연산 식. 15를 이진수로 표현하면 1111이며 (1<<4)로 나타낼 수 있다. 각 자리가 모두 1이므로 모든 도시를 방문한 상태이다. 
  • i=3일 때, 1<<i==1<<3==8이고 이진수로 1000으로 표현한다. v&1000 연산의 결괏값이 0이면 4번째 도시를 방문하지 않은 것으로 판단한다.
• W 리스트를 저장 후 점화식으로 정답을 구한다.

 

https://www.acmicpc.net/problem/14003

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.insert(0,0)

index = 0
maxLength = 1
B = [0]*1000001
D = [0]*1000001
ans = [0]*1000001
B[maxLength] = A[1]
D[1]=1

# 바이너리 서치 구현
def binarysearch(l, r, now):
    while l<r:
        mid = (l+r)//2
        if B[mid]<now:
            l = mid+1
        else:
            r = mid
    return l

for i in range(2, N+1):
    if B[maxLength]<A[i]: # 가장 마지막 수열보다 현재 수열이 큰 경우
        maxLength+=1
        B[maxLength] = A[i]
        D[i] = maxLength
    else: # binarysearch를 이용해 현재 수열이 들어갈 index 찾기
        index = binarysearch(1, maxLength, A[i])
        B[index] = A[i]
        D[i] = index

print(maxLength)
index = maxLength
x = B[maxLength]+1

for i in range(N, 0, -1): # 뒤에서부터 탐색하면서 정답 수열 저장
    if D[i]==index:
        ans[index]=A[i]
        index-=1

for i in range(1, maxLength+1):
    print(ans[i], end=' ')

• D[i] = 0~i까지 i를 포함하는 가장 길게 증가하는 수열의 길이. i를 포함하는 것이 중요함
• A[i]를 i번째 수열의 값이라고 정의하면 D[k]는 A[i]>A[k]를 만족하는 최대 수열의 길이이다. 즉, A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 차자 +1한 후 D[i]에 저장한다.
• D[i] = max({D[k]}) + 1(K=1부터 i-1까지)
• 점화식을 이용해 D 리스트의 값을 저장한다. 이때 자신보다 작은 값을 지니고있는 최장 증가 수열 길이를 찾기 위해 B 리스트를 만든다.탐색은 binarySearch로 구현.
• D 리스트를 이용해 정답을 출력한다. 뒤에서부터 탐색해 최댓값과 동일한 값을 가지는 최초 index의 A[]값을 출력한 후 값을 1만큼 감소시키고 index가 1이 될때까지 반복한다.

---

# 회고

 

점화식은 정말 다양하게 풀 수 있고, 이 문제를 푸는 아이디어를 생각하는게 중요하다.

나는 공식을 적용하는게 좋다...그치만 창의적으로 문제에 대해 생각하고...해답을 만들어내는 것도 연습해야겠지ㅜ