다이나믹 프로그래밍

우리는 연산 속도와 메모리 공간을 최대한으로 활용할수 있는 효율적인 알고리즘을 작성해야 한다.

피보나치 수열

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

print( (fibo(4)))

다이나믹 프로그램 사용 조건

1. 큰 문제를 작은 문제로 나눌수 있다
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

메모이제이션 : 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

다이나믹 피보나치

시간 복잡도 O(N)

# 한번 계산된 결과를 메모이제시연 하기 위한 리스트 초기화 
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))

다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.

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

바텁 업 : 단순히 반복문을 이용하여 작은 문제부터 차근 차근 답을 도출

재귀함수로 비효율적인 프로그램을 작성한 뒤에 메모이제이션을 적용할수 있으면

리팩토링 추천

1로 만들기

1. x가 5로 나누어 떨어지면 5로 나눈다
2. x가 3으로 나누어 떨어지면 3으로 나눈다
3. x가 2로 나누어 떨어지면 2로 나눈다.
4. x에서 1뺀다

입력

• 정수 x 1≤ x ≤30000

$a_i = min(a_{i-1},a_{i/2},a_{i/3},a_{i/5}) +1$

x= int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
d=[0]*30001

for i in range(2,x+1) :
    # 현재 수에서 1 빼는경우 
    d[i] = d[i-1] +1 

    # 현재의 수가 2로 나누어 떨어지는 경우 
    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])

개미 전사

일직선상에서 식량 털어버리기 식량 창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야 한다.

$a_i=max(a_{i-1},a_{i-2}+k_i)$

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

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
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])

첫번째 세번째의 합이 두번째보다 크다면 값을 바꾸는 식

바닥 공사

가로 길이 n 세로길이 2 얇은 바닥

1 x 2 , 2 x 1 , 2 x 2 덮개를 이용해 채우고자 한다.

모든 경우의 수 구하기

i-1 까지의 길이가 덮개로 이미 채워진 경우 2x1 덮개를 채우는 한가지 경우의 수만 존재

i-2 까지의 길이가 덮개로 이미 채워진 경우 1x2 두개 또는 2x2 한개 따라서 2 개의 경우의 수 존재

$a_i = a_{i-1} +a_{i-2}*2 $

효율적인 화폐 구성

화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 m원이 되도록

n: 화폐 종류

m: 가치의 합

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

#DP 테이블 초기화
d= [10001]*(m+1)
d[0]=0
for i in range(n):
    for j in range(array[i],m+1):
        if d[j-array[j]]!=10001:
            d[j] =min(d[j],d[j-array[i]]+1)

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