[이코테] DP

- 연산의 횟수를 비약적으로 줄일 수 있는 알고리즘

 

피보나치 수열

이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열

n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수

 

재귀함수로 나타내기

 

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

이는 동일한 함수를 반복적으로 호출하게 됨.

 

DP의 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

이 문제는 메모이제이션을 이용하여 해결 가능.

한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출할 시에 그 결과를 그대로 가져오는 기법

 

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]

 

퀵 정렬과의 차이점?

퀵 정렬 역시도 DP 와 같이 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어서 문제를 효율적으로 해결함.

그러나 DP 는 퀵 정렬과는 다르게 문제들이 서로 영향을 미침.

퀵 정렬의 경우에는 한번 피벗이 자리를 잡게 되면 더 이상 바뀌지 않지만 DP의 경우에는 다시 해결할 필요가 없는 경우는 미리 구한 답을 반환함

 

큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운 방식

for 문의 경우에는 보텀 업 방식

 

1. 특정 문제가 완전탐색으로 오랜 시간이 걸리면 DP 를 적용할 수 있는지 확인 (부분 문제들의 중복 여부 확인)

2. 메모이제이션을 적용할 수 있으면 코드를 개선

 

+ 탑다운 방식보다는 보텀업 방식을 권장

 

문제 1. 1로 만들기

import sys

x = int(input())

arr = [sys.maxsize for _ in range(x+1)]
arr[1] = 0

for i in range(2,x+1):
    if i%5==0:
        arr[i] = min(arr[i//5]+1,arr[i])
    elif i%3==0:
        arr[i] = min(arr[i//3]+1,arr[i])
    elif i%2==0:
        arr[i] = min(arr[i//2]+1,arr[i])
    arr[i] = min(arr[i-1]+1, arr[i])

print(arr[x])

 

문제 2. 개미 전사

n = int(input())

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

dp = [0 for i in range(n)]

for i in range(n):
    if i==0:
        dp[i] = arr[i]
    elif i==1:
        dp[i] = arr[i]
    elif i==2:
        dp[i] = arr[i-2]+arr[i]
    else:
        dp[i] = max(dp[i-2]+arr[i],dp[i-1])

print(max(dp))

 

문제 3. 바닥 공사

n = int(input())

d = [0]*1001

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

print(d[n])

 

책을 참고해서 풀었다.

바로 이전의 경우에는, 추가적으로는 세로로 한개를 놓는 수밖에 없고 

i-2 의 경우에는 추가적으로 가로로 두개, 정사각형 하나를 놓을 수 있기에 두개이므로 d[i] = (d[i-1]+2*d[i-2]) 이렇게 저장한다.

 

문제 4. 효율적인 화폐 구성

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

#n 개 / m원으로 만들기

money = [
    int(input())
    for _ in range(n)
]

dp = [1001]*(m+1)

dp[0] = 0
for i in range(n):
    for j in range(money[i], m+1):
        if dp[j - money[i]] != 1001:
            dp[j] = min(dp[j], dp[j-money[i]]+1)

print(dp[m])