#6 Python 코딩테스트 다이나믹 프로그래밍(DP)

https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 

이 포스팅은 위의 영상을 보고 제가 필요하다고 생각된 부분을 정리한 포스팅입니다.

 

다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음

구현은 Top - Down , Bottom - Up

 

동적 계획법이라고도 부름

 

문제가 다음의 조건을 만족할 때 사용 할 수 있음.

 

1. 최적 부분 구조 (Optimal Substructure)

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

 

2. 중복되는 부분 문제 (Overlapping Subproblem)

- 동일한 작은 문제를 반복적으로 해결해야 한다.

 

피보나치 수열

큰 문제를 작은 문제로 나눌 수 있는 대표적인 DP의 예시

 

점화식을 활용하면 쉽게 DP 구현

단순 재귀 소스코드

def fibo(x):
    if x ==1 or x ==2:
        return 1
    return fibo(x - 1) + fibo(x - 2)
    
print(fibo(4))

이렇게 소스코드를 작성하게 되면, 지수 시간 복잡도를 가지게 된다.

따라서 DP가 필요함

 

1. 하향식 방법 -> 메모이제이션(Memoization)

- 한번 계산한 결과를 메모리 공간에 메모하는 기법

- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고 하기도 함 

 

다이나믹 프로그래밍의 전형적인 형태는 Bottom - Up 상향식 방식이다.

 

엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념이다.

따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.

탑다운 다이나믹 프로그래밍 소스코드

d = [0] * 100

def fibo(x):
    if x == 1 or x ==2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]
    
print(fibo(99))

 

보텀업 다이나믹 프로그래밍 소스코드

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n + 1):
    d[i] = [i - 1] + d[i -2]

print(d[n])

for loop를 활용하여 보텀업 다이나믹 프로그래밍을 구현

 

위의 함수들의 시간 복잡도는 O(N)으로 구현된 것을 확인

 

다이나믹 프로그래밍 VS 분할 정복

다이나믹 프로그래밍과 분할 정복(퀵 정렬, 이진 탐색)은 모두 최적 부분 구조를 가질 때 사용할 수 있다.

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

 

둘의 차이점은 부분 문제의 중복

- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨.

- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

 

 

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요.

 

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결하 수 있는지 검토.

- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해야 함.

 

일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.

 

일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.

 

개미 전사 문제

 

나의 풀이

N = int(input())
k = list(map(int,input().split()))
dp =[[0] for _ in range(N)]
for i,v in enumerate(k):
    if i ==0 or i==1:
        dp[i] = v
    elif i == 2:
        dp[i] = v+dp[i-2]
    else:
        dp[i] = max(dp[i-2],dp[i-3]) + v
print(max(dp[-1],dp[-2]))

 

답안 예시

 

n = int(input())

array = list(map(int, input().split()))

d = [0] * 100

d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
    d[i] = max(d[i - 1], d[i -2] + array[i])
    
print(d[n - 1])

 

문제의 핵심은 결국 한 칸 건너뛴 창고를 터느냐 두 칸 건너뛴 창고를 터느냐를 선택해서 더 큰 값을 선택하는 것이다.

 

나의 풀이는 무조건 그 창고를 털 경우를 가정한 풀이고

예시 풀이는 그 집을 기준으로 가장 최댓값을 항상 구하는 풀이이다.

 

직관적으로 이해했을 때 예시 풀이가 점화식도 깔끔하고 좋은 풀이 같다.

 

1로 만들기 문제

 

나의 풀이

from collections import deque
X = int(input())
dp = [[False] for _ in range(X+1)]

queue = deque()
queue.append([X,0])
while queue:
    x, answer = queue.popleft()
    if x==1:
        print(answer)
        break
    elif dp[x] ==True:
        continue
    if x%5 ==0:
        queue.append([x//5,answer+1])
    if x%3 ==0:
        queue.append([x//3,answer+1])
    if x%2 ==0:
        queue.append([x//2,answer+1])
    queue.append([x-1,answer+1])

일단 DP 파트이긴 하지만 점화식이 바로 떠오르지 않아서,

최솟값이라는 키워드를 바탕으로 BFS + DP(Memoization)로 풀어봤다.

만약 특정 dp 인덱스에 방문했다면 이미 앞전에 누가 연산을 한 것이므로 연산하지 않았다.

 

정확하게 모든 테스트 케이스에서 동작하는진 모르겠지만 일단 시간 복잡도가 O(N)인 것 같다.

 

답안 예시

x = int(input())

d = [0] * 30001

for i in range(2, x + 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)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)
    
print(d[x])

답안 예시는 정석적으로 깔끔한 코드 같다. 확실히 난 아직 점화식이 익숙지 않은 것 같다.

 

효율적인 화폐 구성 문제

 

나의 풀이

from collections import deque
n, m = map(int, input().split())
money = []
for i in range(n):
    money.append(int(input()))
dp = [False for _ in range(m+1)]
queue = deque()
queue.append([m,0])
while queue:
    answer, count = queue.popleft()
    if answer ==0:
        print(count)
        break
    for coin in money:
        if answer - coin >=0:
            if dp[answer-coin] ==True:
                continue
            dp[answer-coin]=True
            queue.append([answer-coin,count+1])
if dp[0] == False:
    print('-1')

역시 마찬가지로 Top down 방식으로 deque를 활용해서 풀었다. 시간 복잡도는 O(NM)이다.

 

답안 예시

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

array = []
for i in range(n):
    array.append(int(input())

d = [10001] * (m + 1)

d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001 # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

if d[m] == 10001:
    print(-1)
else:
    print(d[m])

 

이번 문제 예시를 보면서 DP를 보텀업 방식으로 풀 때에는,

출력해야 하는 결괏값을 기반으로 점화식을 작성하는 게 좋다고 느꼈다.

 

금광 문제

 

나의 풀이

T = int(input())

for _ in range(T):
    n, m  = map(int,input().split())
    array = list(map(int,input().split()))
    array.reverse()
    gold_mine =[[0]*m for _ in range(n)]
    dp =[[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            gold_mine[i][j]=array.pop()
            if j==0:
                dp[i][j] = gold_mine[i][j]
    for j in range(1,m):
        for i in range(n):
            if i == 0: # i 가 0 일때
                if n ==1:# 한 줄
                    dp[i][j] = gold_mine[i][j] + dp[i][j-1]
                else: # 아래 있을 때
                    dp[i][j] = gold_mine[i][j] + max(dp[i][j-1],dp[i+1][j-1])
            elif i == n-1: # 아래 없을 때
                dp[i][j] = gold_mine[i][j] + max(dp[i-1][j-1],dp[i][j-1])
            else : #위도 있고 아래도 있을 때
                dp[i][j] = gold_mine[i][j] + max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])
    answer = 0
    for i in range(n):
        if dp[i][-1] > answer:
            answer = dp[i][-1]
    print(answer)

답안 예시

for tc in range(int(input())):
    n, m = map(int, input().spit())
    array = list(map(int, input().split()))
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index + m])
        index += m
    for j in range(1, m):
        for i in range(n):
            # 왼쪽 위
            if i ==0: left_up =0
            else: left_up = dp[i - 1][j - 1]
            # 왼쪽 아래
            if i == n - 1: left_down = 0
            else: left_down = dp[i + 1][j - 1]
            # 왼쪽 중간
            left = dp[i][j - 1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)
    result =0
    for i in range(n):
        result = max(result, dp[i][m -1])
    print(result)

이번에 답안 예시 로직이 아예 똑같다. 근데 확실히 답안 예시에서 뭔가 내공이 느껴졌다.

일단 나는 금광이랑 dp를 따로 초기화했는데, 그럴 필요가 없었고 left_up , left_down을 따로 선언한 게 코드 가독성이 훨씬 올라간 것 같다.

 

병사 배치하기

이 문제는 가장 긴 증가하는 부분 수열 (LIS) 알고리즘을 확인해서 풀이할 수 있다.

 

D[i] => array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

 

- 점화식

# 모든 0<= j < i에 대하여, 
D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

 답안 예시

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

array.reverse()

dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
    for j in range(0, i):
        for array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))