다이나믹 프로그래밍 (동적 계획법)
- 메모리 공간을 조금 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법
- 사용조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.재귀적 구현
dyna = [0] * 100
def pibo(x):
if x == 1 or x == 2:
dyna[x] = 1
return 1
elif dyna[x] != 0:
return dyna[x]
else:
dyna[x] = pibo(x-1) + pibo(x-2)
return dyna[x]
print(pibo(99))- 탑다운(메모이제이션, 캐싱, 하향식) 방식 : 큰 문제를 해결하기 위해 순차적으로 작은 문제를 호출하며 해결하는 방식
반복적 구현
dyna = [0] * 100
def pibo(x):
dyna[1], dyna[2] = 1, 1
if x == 1 or x == 2:
return 1
for i in range(3,x+1):
dyna[i] = dyna[i-1] + dyna[i-2]
return dyna[i]
print(pibo(99))- 보텀업 방식(상향식): 작은 문제부터 답을 도출해나가는 방식
- DP 테이블 : 보텀업 방식에서 사용되는 결과 저장용 리스트문제 1. 1로 만들기 (난이도 1.5, 40분/20분)
#6:01
#X가 5로 나누어 떨어지면 5로 나눔
#X가 3으로 나누어떨어지면 3으로 나눔
#X가 2로 나누어 떨어지면 2로 나눔
#X에서 1 뺌
#1로 만들때까지 연산의 최소값
#나누어 떨어질 수 있는 수 중에 제일 큰 것 선택
#없으면 1 뺌
val = int(input())
dyn = [0]*30001
# for i in range(1,30001):
# if i % 5 == 0:
# #dyn5[i] = 1
# dyn[i] = 1
# if i % 3 == 0:
# #dyn3[i] = 1
# dyn[i] = 1
# if i % 2 == 0:
# #dyn2[i] = 1
# dyn[i] = 1
dyn[1] = 0
for i in range(2,val+1):
comp = []
if i % 5 == 0:
comp.append((dyn[int(i/5)],int(i/5)))
if i % 3 == 0:
comp.append((dyn[int(i/3)],int(i/3)))
if i % 2 == 0:
comp.append((dyn[int(i/2)],int(i/2)))
comp.append((dyn[int(i-1)],int(i-1)))
comp = sorted(comp, key=lambda x: x[0])
min_before = comp[0][1]
dyn[i] = dyn[min_before] + 1
print(dyn[val])
# while val != 1:
# if dyn5[val] == 1:
# val = int(val / 5)
# elif dyn3[val] == 1:
# val = int(val / 3)
# elif dyn2[val] == 1:
# val = int(val / 2)
# else:
# val -= 1
#
# cnt += 1
print(cnt)
빙빙 돌았다.
처음엔 다이나믹프로그래밍이 아니라 아예 순차적 계산을 생각했다가 26이란 입력값에서 바로 반례발견.
다이나믹으로 해결법을 떠올렸지만 구현 과정이 좀 더러워짐.
값을 비교한다고 리스트에 튜플까지 썼는데 책을 보니 어차피 두 값끼리만 비교하면 되는거라 더 간단해질 수 있었음.
dyn[i] = dyn[i-1] + 1 #이미 1을 뺐다고 가정하고 값을 초기화
if i % 2,3,5 == 0: #1을 뺀 것과 2,3,5를 나눈 것과 순서대로 비교
dyn[i] = min(dyn[i],dyn[i // 2,3,5] + 1 # // 연산은 결과가 정수로 나오니 이걸 써야했음
꿀팁
- 점화식을 떠올려보자 : A i의 연산 최소값은 i-1, i/2, i/3, i/5의 연산 최소값 중 제일 작은 것에서 1을 더한 것
A = min(A,A<i/2>,A<i/3>,A<i/5>) + 1
문제 2. 개미 전사 (난이도 2, 완패/30분)
#7:05
N = int(input())
data = list(map(int,input().split()))
food = [0]*N
# [1,10,2,9,1000,3,8,4,7,5,6]
# 1. 500. 1,1000. 1,1000. 1,1000,1000.
# 1, 100 , 100 ,100 ,100 ,500 ,1000
# i 번째 식량에 도착했을 때 i-2까지 먹은 식량 + i식량과 i-1까지 먹은 식량을 비교했을 때 큰것이 i번째까지 먹은 것
# a<i> = max(a<i-1>, a<i-2>+ food<i>)
food[0] = data[0]
food[1] = max(data[0],data[1])
for i in range(2,N):
food[i] = max(food[i-1],food[i-2]+data[i])
print(food[N-1])
하나하나 계산적으로 따지는 것 보다 오히려 추상적으로 접근해서 생각하는 연습을 할 필요가 있을 듯
# i 번째 식량에 도착했을 때 i-2까지 먹은 식량 + i식량과 i-1까지 먹은 식량을 비교했을 때 큰것이 i번째까지 먹은 것
이 생각 하나만으로 문제 해결인데 너무 직접 많은 경우의 수를 떠올리다 망함.
문제 3. 바닥 공사 (난이도 1.5, 풀이시간 50분/20분, 틀림)
#6:34
#네모가 하나 들어갈 수 있으면 3개의 가지수
N = int(input())
data = [0] * 1001
data[1] = 1
data[2] = 3
data[3] = 5
data[4] = 11
for i in range(5, N+1):
data[i] = data[i-1] + data[i-2]*2
print(data[N]%796796)
끝이 될 수 있는 경우 3가지만 고려하면 되는데 너무 복잡하게 생각했음.
문제 4. 효율적인 화폐 구성 (난이도 2, 풀이시간 50분/30분)
#3:50
#n가지 화폐를 최소갯수으로 이용하여 m원이 되도록
#화폐의 조합은 순서가 달라도 같은걸로
#화폐개수 출력. 불가능시 -1
#2,3 -> 15 => 5
N, M = list(map(int,input().split()))
kind = []
min_money = [0] * 10001
for i in range(N):
kind.append(int(input()))
#i원의 최소개수 = i-2원의 최소개수 존재 or i-3원의 최수개수 존재 둘다 존재시 최소개수가 적은거 + 1, 둘다 없으면 -1
kind = sorted(kind)
for i in kind:
min_money[i] = 1
#1원부터 M원까지
#화폐종류마다
#지금 화폐보다 액수가 클때만
#처음 검사하는거고 이전액수의 최소갯수가 존재할 때
#현재액수최소개수 = 이전액수최수개수 + 1
#두번째화폐검사하는거고 이전액수의 최소개수가 존재할 때
#현재액수최소개수보다 지금 이전액수최소개수 + 1이 더 작을때
# 현재액수최소개수 = 이전액수최수개수 + 1
#[처음이거나 두번째인데 (두번째검사의 액수의 최소개수가 0 일리가 없으므로 사실상 처음)]이전 액수의 최소개수가 존재하지 않으면
#현재액수최소개수 = -1
for i in range(1,M+1):
for x in kind:
if i-x > 0:
if min_money[i] == 0 and min_money[i-x] >= 1:
min_money[i] = min_money[i - x] + 1
elif min_money[i] > 0 and min_money[i-x] >= 1:
if min_money[i] > min_money[i-x] + 1:
min_money[i] = min_money[i-x] + 1
elif min_money[i] == 0 and min_money[i-x] <= 0:
min_money[i] = -1
elif i == x:
min_money[i] = 1
print(min_money[M])
최소개수가 없는 경우(=만드는 방법이 존재하지 않는 경우)를 0 과 -1을 혼용하여써서 헷갈림.
그냥 통일하고 결과값에서만 바꿔주면 되는데.
이전 최소개수값이 있는 경우 -> min(min_money[i], min_money[i-x] + 1) 이면 끝인데 너무 조건문으로 바꾸려다보니 장황해짐.
스케치를 조건문 그대로 구현하려하지말고 좀 더 생각해볼 것
그리고 kind 리스트의 원소마다 전체를 돌리는 식으로 했으면 시작인덱스값을 편하게 설정할 수 있어 오히려 간단했을 것.