[코딩테스트] 다이나믹 프로그래밍

다이나믹 프로그래밍

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

계산된 결과를 메모리 영역에 저장하여 다시 계산하지 않도록 함

 

최적 부분 구조와 중복 부분 문제가 만족할 때 사용 가능함

최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있는 경우

중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 하는 경우

 

점화식 : 인접한 항들 사이의 관계식

 

 

메모이제이션

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

같은 문제를 다시 호출하면 메모한 결과를 가져옴

캐시이라고도 함

결과 저장용 리스트를 DP 테이블이라고 부름

 

 

탑다운 : 위에서 아래로 내려감, 큰 문제 해결을 위해 작은 문제들을 재귀적으로 호출하여 작은 문제를 먼저 해결

보텀업 : 아래서부터 위로 올라감, 아래쪽부터 작은 계산문제를 하나씩 해결 (반복문 이용)

작은 문제를 먼저 해결해서 점차 올라감

 

 

피보나치 수열

재귀함수를 통해 단순히 구현한다면 중복되는 계산이 발생할 수 있음

 

- 탑다운 방식 피보나치 해결 방법

d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0: # 계산한 적 있는 문제라면
        return d[x] # 계산 결과를 가져옴
    else: # 계산한 적 없는 문제라면
        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] = d[i - 1] + d[i - 2]

print(d[n])

 

 

vs 분할 정복

다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용이 가능함

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

 

 

풀이 알고리즘 선택 방법

주어진 문제가 그리디 , 구현, 완전 탐색으로 해결 가능한지 검토

완전 탐색으로 너무 많은 시간 복잡도가 들게 되면 다이나믹 프로그래밍을 검토

작은 문제를 조합하여 큰 문제를 풀 수 있음, 중복되는 특성을 가짐 -> 다이나믹 프로그래밍

-> 앞부분에서 계산한 결과가 이후 계산할 결과에 영향을 미치는 경우

-> 점화식이 있는 경우 다이나믹  프로그램 -> 점화식을 찾는 것이 중요함!

(다이나믹 프로그래밍 문제는 기본 유형의 문제가 기본적으로 나오기 때문에 반복적인 습득이 필요) 

 

 

다이나믹 알고리즘 풀이 방법

큰 문제를 통해서 작은 문제를 풀 수 있는가? O

점화식을 도출해야 함!!!!!!!!!!!!!!

DP 테이블 초기화

탑다운/보텀업 중 하나를 선택하여 문제를 해결하면서 작은 결과 값을 DP 테이블에 저장

문제 해결 공식은 도출된 점화식을 그대로 사용

 

 

문제) 개미 전사

N개의 창고가 붙어 있을 때 최대한 많은 양의 식량을 털어야함

서로 붙어 있는 창고는 털 수 없음

 

왼쪽부터 하나씩 계산하면됨

dp[i]를 i 번째까지의 최적의 해라고 가정

data[i] = i번째 창고의 식량 양

i-1번째 창고를 털었다면 i번째 창고를 털 수 없음

-> max(dp[i-1]), dp[i-2] + data[i]) 

보텀업 방식 사용함

n = int(input()) # 식량 창고의 개수

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

dp = [0] * 100

dp[0] = data[0] # 첫 번째 창고만 터는 경우
dp[1] = max(data[0], data[1]) # 첫 번째와 두 번째 창고를 터는 경우

for i in range(2, n):
    dp[i] = max(dp[i-1], dp[i-2] + data[i]) # 점화식 그대로 작성

print(dp[n - 1])

 

 

문제) 1로 만들기

정수가 주어졌을 때 (1 <= x <= 30000), 5, 3, 2로 각각 나누어 떨어지면 해당 값으로 나누기

나누어지지 않으면 -1 연산 수행

을 하여 1이 되도록 하는 최소 연산 횟수 구하기

 

그림을 그려보면 트리구조

작은 계산으로 큰 계산이 가능하므로 다이나믹 알고리즘

dp 테이블 생성

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) # 뒤에 붙은 1은 이번에 계산하는 횟수
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1) # d[i // n]은 이번 계산 후 1이되기 까지 최소 횟수 계산
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

 

 

문제) 효율적인 화폐 구성

N가지 종류의 화폐를 사용하여 그 합이  M원이 되도록하는 최소한의 화폐 개수 구하기

출력은 최소 화폐 개수이며, 불가능한 경우 -1 출력

 

dp[i] = 금액 i를 만들 수 있는 최소 화폐 개수

k = 각 화폐 단위 

 

- 아이디어

각 화폐 단위를 작은 순서대로 따로 따로 확인하자 (이중 for문)

ex) 2, 3원짜리 화폐 단위 확인

 

무한(한계치를 넘어가는) 값으로 초기화

0원을 0으로 초기화

한 칸씩 올라가면서 이전 값 + 단위 값을 통해 i를 만들 수 있는지 여부를 판단 (i-k를 만드는 방법이 존재하는 경우)

만들 수 있으면 이전 값을 만들 때 사용한  화폐 개수 + 1

-> dp[2]는 dp[0]가 0이기 때문에 0+1 

-> 이때 이전 값은 현재 dp[인덱스-현재 화폐 단위]로 확인 가능함

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

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

dp = [10001] * (m+1) # 10001 == 만들 수 없는 값으로 가정

dp[0] = [0]
for i in range(n): # 화폐 단위만큼 반복
    for j in range(money[i], m+1): # 화폐 단위부터 끝까지 반복
        if dp[j - money[i]] != 10001: # (현재 탐색 가격 - 화폐 단위)가 계산 가능하다면
            dp[j] = min(dp[j], dp[j - money[i]] + 1) # min(기존의 연산, 이전 계산 횟수 + 1)

if dp[m] == 10001: # 계산 방법이 없는 경우
    print(-1)
else:
    print(dp[m])

 

 

 

 

※ 해당 포스트는 이것이 "코딩 테스트다 with 파이썬(나동빈 저)"를 통해 학습한 내용을 정리한 것입니다.