파이썬(python) 알고리즘 - 동적 계획법 푸는 방법

DP문제를 풀어나가는 순서

1. 문제의 조건대로 손으로 그려보며 반복되는 부분을 찾습니다.

 

2. dp테이블 dp[i]는 무엇을 의미하는지 정의해봅니다.  

dp[i] = ???

 

3. 디테일한 점화식을 세웁니다.

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

 

4. 필요하다면 dp 테이블을 확장합니다.

dp[i] → dp[i][j]

 

5. 중복되는 부분을 어떻게 활용할 수 있을지 생각합니다.

어떤 방법으로도 점화식 세워지지 않으면 계산 과정이나 정의의 순서를 뒤집어서 생각해봅니다.

예를 들면 계산 과정을 완전히 거꾸로 뒤집어보는 발상을 해봅니다.

즉 1+1=2 이 아니라 2=1+1 이라는 발상을 하는 것입니다.

1번으로 되돌아가서 다시 진행합니다.

 

DP문제 유형이라고 어떻게 판단하는가?

문제만 보면 완전 탐색과 그리디와 헷갈릴 수 있다.

완탐이라기엔 시간이 부족하고

그리디라기엔 항상 탐욕적으로 취해서는 최적해가 나오지 않는다.

 

 

문제 예시를 통해 알아보기

동적 계획법 1 단계

 

아래는 제가 문제 풀면서 생각했던 과정을 녹여보았습니다.

백준 1463 : 1로 만들기

1463번: 1로 만들기

순서	내용
1. 손으로 그려보며 반복되는 부분 찾기	10 → 5 → 4 → 2 → 1 10 → 9 → 3 → 1  9 → 3 → 1  3 → 1
2. dp테이블 dp[i] 의미 정의	dp[i] = i번 연산했을때 최소값
3. dp테이블 채우는 시뮬레이션 해보며 디테일한 점화식을 세우기	n=10 일때 1번 연산했을때 10//2 → 5 혹은 10-1 → 9  1번 연산했을때 최소값인 5를 택하는 것 보다 9를 택하는게 더 나음. 하지만 끝까지 가보면 9를 택하는 것이 더 나은 선택임. 10 → 5 → 4 → 2 → 1 10 → 9 → 3 → 1 처음 정의로는 점화식 세우기 불가능. 다른 정의가 필요함.
4. 점화식 세워지지 않으면 계산 과정이나 정의의 순서를 뒤집어봅니다.	정의에서 앞뒤 순서를 바꿔보니 위의 문제가 해결됨. n에서 1로 내려가는 것이 아니라 1에서 부터 시작해서 n을 만드는 방법을 찾는 것임. n=10은 1+1+1+1+1+1+1+1+1+1 = 10회 연산 1*2*2*2+1+1 = 5회 연산 1*3*3+1 = 3회 연산 기존 : dp[i] = i번 연산했을때 최소값 변경 : dp[i] = i라는 숫자를 만들 수 있는 최소 연산 횟수
5. 재정의된 dp테이블로 시뮬레이션	n=10 일때 1번 연산했을때 10 → 5 혹은 10 → 9  1번 연산했을때 최소값인 5를 택하는 것 보다 9를 택하는게 더 나음. 10 → 5 → 4 → 2 → 1 10 → 9 → 3 → 1

 

최종 풀이

dp[i] = i라는 숫자를 만들 수 있는 최소 연산 횟수

1부터 n까지 차례로 올라가면서
*2, *3, +1을 하여 값을 만들어가며 해당 값을 만든 최소연산횟수 갱신

import sys
dp = [int(1e9)] * 3000003
n = int(sys.stdin.readline())
dp[1] = 0

for i in range(1, n+1):
    dp[i*2] = min(dp[i*2], dp[i]+1)
    dp[i*3] = min(dp[i*3], dp[i]+1)
    dp[i+1] = min(dp[i+1], dp[i]+1)
print(dp[n])

 

백준 10844 : 쉬운 계단 수

10844번: 쉬운 계단 수

 

순서	내용
1. 손으로 그려보며 반복되는 부분 찾기	n=1 일때 1~9 : 9개 n=2 일때  1 뒤에 0,2 가 올 수 있음 = 10, 12 1 앞에 2가 올 수 있음 = 21 2 뒤에 1,3 가 올 수 있음 = 21, 23 2 앞에 1,3 가 올 수 잇음 = 12, 32 ... 9 뒤에 8만 올 수 있음 = 98 9 앞에 8만 올 수 있음 = 89
2. dp테이블 dp[i] 의미 정의	특정 수의 앞뒤로 숫자를 끼워넣어서 새로운 숫자를 만드려고 하니, 불필요한 중복이 생겨버림
3. 중복되는 부분을 어떻게 활용할 수 있을지 생각해봅니다.	우선 특정 수의 뒤에만 숫자를 끼워넣어서 새로운 숫자를 만들도록 변경 n=1 일때 1~9 : 9개 n=2 일때  0 뒤에 1이 올 수 있음 = 01 1 뒤에 0,2 가 올 수 있음 = 10,12 2 뒤에 1,3 가 올 수 있음 = 21, 23 ... 8 뒤에 7,9 가 올 수 있음 = 87, 89 9 뒤에 8만 올 수 있음 = 98 n=3 일때 10 뒤에 1 올 수 있음  = 101 12 뒤에 1,3 올 수 있음 = 121, 123 10에서 0 뒤에 1이 온다는것을 이미 알고 있었음. 12에서 2뒤에 1이나 3이 와서 2개의 숫자를 만들 수 있다는 것도 암. 이것을 이용하여 dp테이블 정의가능. dp[i][j] = i라는 숫자로 시작하는 길이 j의 숫자 개수
4. 재정의된 dp테이블로 시뮬레이션	dp[0][2] = 01 (1개) dp[1][2] = 10, 12 (2개) dp[2][2] = 21, 23 (2개) ... dp[8][2] = 87, 89 (2개) dp[9][2] = 98 (1개) dp[0][3] = 010, 012 (2개) = 0 + dp[1][2] dp[1][3] = 121, 123 = 1 + dp[2][2]            = 101 = 1 + dp[0][2] ... dp[9][3] = 987, 989 = 9 + dp[8][2] 시뮬레이션 해보면 3가지 경우가 나오는 것 확인할 수 있다. 1) 0으로 시작할때 2) 9로 시작할때 3) 그외의 숫자로 시작할때
5. 점화식 디테일하게 세우기	for length in range(2,n+1):     for num in range(0,10):         if num == 0:             dp[num][length] = dp[num+1][length-1]         elif num == 9:             dp[num][length] = dp[num-1][length-1]         else:             dp[num][length] = dp[num+1][length-1] + dp[num-1][length-1]

 

최종 풀이

dp[i][j] = i라는 숫자로 시작하는 길이 j의 숫자 개수

길이 j가 1일때 모두 1로 초기화 후 n까지 차례로 길이 늘려가며 진행

시작하는 숫자 i가 0, 9, 그외 일때 3가지로 나누어서 진행

import sys
n = int(sys.stdin.readline())
dp = [[0]*(n+1) for _ in range(10)]

for i in range(0,10):
    dp[i][1] = 1

for length in range(2,n+1):
    for num in range(0,10):
        if num == 0:
            dp[num][length] = dp[num+1][length-1]
        elif num == 9:
            dp[num][length] = dp[num-1][length-1]
        else:
            dp[num][length] = dp[num+1][length-1] + dp[num-1][length-1]

total = 0
for i in range(1,10):
    total += dp[i][n]
print(total%1000000000)

 

 

백준 11053 : 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

순서	내용
1. 손으로 그려보며 반복되는 부분 찾기	arr = 10 20 10 30 20 50 10 20 30 50 을 취하면 됨 30과 50을 취할때도 앞의 결과 (10 20)는 바뀌지 않음.
2. dp테이블 dp[i] 의미 정의	i번째 까지 취할 수 있는 가장 긴 수열의 길이
3. 중복되는 부분을 어떻게 활용할 수 있을지 생각해봅니다.	1부터 n까지 순서대로 하나씩 자신의 이전 값 까지만 검사. 가장 긴 수열의 길이를 업데이트하고 이 값을 그 다음에도 활용.
4. 점화식 디테일하게 세우기	for cur in range(1, n):     for front in range(0, cur):         if arr[front] < arr[cur]:             dp[cur] = max(dp[cur], dp[front]+1)

 

최종 풀이

dp[i] = i번째 까지 취할 수 있는 가장 긴 수열의 길이

dp = [1]*n : 처음에 모두 다 길이 1(자기자신)의 수열이라고 보고 1로 초기화 

1부터 n까지 순서대로 진행하며 자신의 이전 값 중에서 자신보다 작은 가장긴 수열길이 + 1로 개신
이 값을 그 다음 순서에서도 활용가능.

import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1]*n
for cur in range(1, n):
    for front in range(0, cur):
        if arr[front] < arr[cur]:
            dp[cur] = max(dp[cur], dp[front]+1)
print(max(dp))

 

백준 9251 : LCS

9251번: LCS

최초 접근법 (풀이아님)

이 문제를 처음에는 가장 긴 증가하는 부분수열 (LIS)와 비슷하게 접근했다. 2번 배열의 각 요소가 1번 배열에서 몇 번째 인덱스인지 기록하고, LIS처럼 풀어버리면 되지 않을까 생각했다. 문제는 같은 알파벳이 여러 번 등장하는 경우였다. index 012345 arr1  ACAYKP   arr2  CAPCAK 에서 105124, 105104, 125104, 125124 와 같은 여러 가지 경우가 나와버린다. 사람 머리속으로 생각하면 105124가 나와서 0124 순서로 이으면 답이 4가 나오는데 이를 처리하는데 또 불필요한 추가 연산이 들어가는게 영 아닌것 같아서 중단했다.

 

최종 풀이

dp[i][j] = arr1[:i+1] 과 arr2[:j+1] 의 LCS 길이

1번 리스트의 i번까지의 문자열과

2번 리스트의 j번까지의 문자열의 공통되는 부분 수열의 최장 길이

시도	결과
A → i C → j	공통 부분 수열 못만든다.
A  → i CA→ j	A로 1개 만들 수 있다.
AC CA	CA로 2개 만들 수 있다. arr1[i] == arr2[j] 이면 길이 1이 추가됨을 알 수 있다.
ACA CAP	arr1[i] != arr2[j]이면? 이전 문자열로 만들 수 있던 최대 길이를 가지면 된다. 왜냐면 CA로 2개를 만들 수 있다는 사실은 변함이 없다.
CAP ACA	arr1[i] != arr2[j]인데 이런 경우도 있을 수 있다. [i-1][j] 와 [i][j-1] 중에서 큰것을 취해야 한다. arr1[i] != arr2[j] 일땐 max(dp[i-1][j], dp[i][j-1]) 값을 가져야 한다.

import sys
arr1 = ' ' + sys.stdin.readline().rstrip()
arr2 = ' ' + sys.stdin.readline().rstrip()

a_len = len(arr1)
b_len = len(arr2)
dp = [[0] * (b_len) for _ in range(a_len)]

for i in range(1, a_len):
    for j in range(1, b_len): 
        if arr1[i] == arr2[j]: 
            dp[i][j] = dp[i-1][j-1] + 1 
        else: 
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
print(dp[a_len-1][b_len-1])

 

 

백준 12865 : 평범한 배낭

12865번: 평범한 배낭

순서	내용
1. 손으로 그려보며 반복되는 부분 찾기	n=4, k=7 6 13 → 무게가 6이되어 더이상 추가불가 5 12 → 무게가 5이므로 더이상 추가불가 4 8 → 무게가 4이므로 최대 3까지 추가 가능 3 6 → 무게 여유가 있어서 추가 가능 4 10 → ??? (4,8), (3,6) → (7,14) (3 6), (4 10) → 이렇게 택하면 (7,16) 으로 최대가 나온다.
2. dp테이블 dp[i] 의미 정의	i번째 까지 물건을 택했을때의 최대 가치
3. 무게를 어떻게 저장 할 것인가?	선택지는 두가지다. i번 물건을 가방에 1) 넣는다 2) 안 넣는다. → 백트래킹으로도 풀 수 있을 것으로 보인다. 하지만 무게는 어떻게 저장할 것인지가 고민이다.
4. dp 테이블 확장하기 dp[i] → dp[i][j]	i번에서 j번까지 물건을 택했을때의 최대 가치
5. 확장된 테이블로 시뮬레이션	도저히 시뮬레이션 불가. 포기
6. dp 테이블 재정의 dp[i][w]	i번째 까지 물건을 택했을때의 최대 가치 이 때의 무게를 w라고 정의
7. 점화식 디테일하게 세우기	1) i번 물건 택한 경우 dp[i][w] = max(dp[i-1][w],dp[i-1][w-arr[i][0]] + arr[i][1])  2) i번 물건 택하지 않은 경우 dp[i][w] = dp[i-1][w]

 

최종 풀이

dp[i][w] = i번째 까지 물건 취했을때 무게w로 만들 수 있는 최대 가치

dp[i] 라는것은 i번 까지의 물건을 택했을때의 최대가치다.

for 물건 i를 택했을때

for 무게를 1부터 최대한도까지 차례로 증가시켜본다.

  i번 물건의 무게가 더 무거우면 i-1번 까지 택했을때 최대가치를 저장

  = dp[i-1][w]

 

  i번 물건의 무게가 크거나 같으면 가방에 담을 수 있다.

  이때 담을지 안 담을지 선택이 가능하다. 가치가 큰 쪽을 선택.

  1) i를 담지 않는다. = dp[i-1][w] 

  2) i를 담는다. = dp[i-1][w-arr[i][0]] + arr[i][1]

     → 현재 무게를 빼줘야 담아진다. 이런 생각이 제일 어려운것 같다. ㅠㅠ

import sys
n,k = map(int, sys.stdin.readline().split())
arr = [(0,0)]+[tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1):
    for w in range(1,k+1):
        if w >= arr[i][0]:
            dp[i][w] = max(dp[i-1][w],dp[i-1][w-arr[i][0]] + arr[i][1]) # 택한 경우
        else : 
            dp[i][w] = dp[i-1][w] # 택하지 않는 경우
print(dp[n][k])