DP는 메모이제이션으로 풀자
- 재귀를 쓸때도 있다!
- 단, 메모장의 해당 인덱스에 값이 있다면(=방문한 적 있다면) 계산 X하고 걔를 활용해준다- 즉, 계산 전에 전처리하는 것
if d[x] != 0:
return d[x]- 그리디랑 차이점은 = 그리디는 나누기 5가 되면 나누기 5 먼저해서 나머지 값에서 -1-1-1 이렇게함
Bottom Up - 피보나치
- 3부터 시작!!
''' Python - 피보나치수열 - Bottom Up (주로 사용) - O(N) '''
# (중요) 한 번 계산된 결과를 메모이제이션하기 위한 리스트 생성
d = [0]*100
# 첫 번째 피보나치 수와 두 번째 피보나치 수 저장
d[1] = 1
d[2] = 1
n = 99
# 바텀업 다이나믹 프로그래밍
for i in range(3, n+1): # (중요) 3번째부터 계산해나감
d[i] = d[i-1] + d[i-2] # 매번 계산해서 넣어줌(=메모)한다고 생각
print(d[4])
print(d[6])Top Down - 피보나치
- 메모장의 해당 인덱스에 값이 있다면(=방문한 적 있다면) 계산 하지 않고 걔를 활용
''' Python - 피보나치수열 - Top Down - O(N) '''
# (중요) 한 번 계산된 결과를 메모이제이션하기 위한 리스트 생성
d = [0]*100
# 탑다운 다이나믹 프로그래밍
def fibo(x):
print('f(', str(x), ')', end=' ')
# 종료 조건 : 배열의 첫 또는 두 번째일 때 1 반환(=이걸 해줘야 다음 값을 더하면서 연산 가능)
if x == 1 or x == 2:
return 1
# (개중요) 재귀 Break!!! 만약 이미 계산한 적 있는 문제일 경우 결과값 그대로 반환
if d[x] != 0:
return d[x]
# (중요) x에 대해 계산하는데, recursive하게 f(1), f(2)까지 함수 호출하여 연산 수행
# -> 만약 아직 계산하지 않았던 문제라면 점화식에 따라 피보나치 결과 반환
d[x] = fibo(x-1) + fibo(x-2)
return d[x] # 원하는 x번째 값을 연산했으니 리턴
print(fibo(4)) # 앞서 작성한 코드보다 매우 빠르게 수행됨!
print(fibo(6)) # 앞서 작성한 코드보다 매우 빠르게 수행됨!
1. 1로 만들기 - 동빈나 예제 (백준에도 있음)
x - 1한 걸 베이직으로 배열 d의 x번째 인덱스 d[x]에 넣어두고
**if를 병렬**로 하여 각각 Best로 작은 걸 저장
d[x] = ( d[x-1 위치] + 1 vs d[x//2 위치] + 1 ) <-- 둘 중 작은거
d[x] = ( 둘중 작은 애 vs d[x//3 위치]] + 1 )- 즉, 배열 d에는 counting 횟수가 들어가고,
- 이동횟수가 최소가 되야 하므로, 그 counting 횟수가 가장 적은 값을 넣어줌- 이때 x는 index값임(=위치)
- x = 6일 때 경우의 수가 3개가 있는데,
- memo(5)는 x-1일 때 최적의 해를
- memo(3)는 x//2일 때 최적의 해를
- memo(2)는 x//3일 때 최적의 해를 갖고있음- 이중에서 min값을 memo[x]에 저장하면 됨
- 즉, d[x]에 들어갈 값은
- [x-1]에서의 값- [x//2]에서의 값
- [x//3]에서의 값
- [x//5]에서의 값
- 을 중 최소값
''' python '''
#x = int(input())
a=26
d = [0] * 100 # 카운팅하는 값(=호출된 횟수)이 들어감
for x in range(2, a+1): # x는 인덱스값이고
d[x] = d[x-1] + 1 # d[6]에 d[5]가 한번 "카운팅"됨 = "+1"
if x % 2 == 0: # f[6]이 2로 나눠질 경우,
d[x] = min(d[x//2]+1, d[x]) # f[6//2]에 +1을 카운팅했을 경우와 f[6-1] 카운팅 수 중 작은 카운팅을 재정의
if x % 3 == 0:
d[x] = min(d[x//3]+1, d[x]) # f[6//3]에+1 한것과 f[6//2]+1 와 f[6-1] 중 비교
if x % 5 == 0:
d[x] = min(d[x//5]+1, d[x])
print(d[:27])
print(d[a])
그리디와 DP 차이점
-
만약 위 문제에서 26이란 값이 있을 때,
- 그리디 : 2로 먼저 나눠 -> 13 만들어 -> -1하고 2로 나눠 -> 6 만들어 이런 식인데
=> 즉, (=나눠서 나온 값이 제일 작아지게 만든다)- DP : 1로 먼저 빼줘서 더 빠르게 값에 도달하도록(연산 줄이도록)
이쯤 느낀 것 : DP는 메모이제이션이랑 min(a,b), max(a,b) 가 핵심인듯
~> {새로운거 k vs 이전꺼 memo}의 count를 min/max 비교 후 현재 위치[i]에 메모
- 그리고 수식 세우기
2. 개미전사
- 즉 여기가 핵심
- i-1위치를 털었음 : 바로 다음인 i는 못텀 => [i-1]위치의 값이 최적의 해- i-2위치를 털었음 : i는 털 수 있음 => [i-2] + [i]가 최적의 해
- (핵심은) memo[]가 최적의 해를 매 index마다 기록하고
- 그래서 메모에 기록된 값과 새로운 k[i]를 계속 비교해나가는 것!!!
''' python '''
#n = int(input())
#k = list(map(int, input().split()))
k = [1,3,1,5,2,4,6,1]
#k = [1,3,1,5]
n = len(k)
memo = [0]*n
memo[0] = k[0] # (핵심은) 얘네만 미리 박아줌
memo[1] = max(k[0], k[1])
for i in range(2, n):
# 새로운거 vs 이전꺼 min/max 비교 후 현재 위치에 메모
memo[i] = max(memo[i-1], memo[i-2] + k[i])
# d[i-2]를 활용하는 이유는 d[i-2]에 있는 숫자가 d[i-4]에 있는 수를 ... recursive하게 값을 갖고있음
print(memo)
print(memo[-1])
3. 효율적인 화폐 구성
-
각 문제 해결전략마다 나오지만
- a_i가 최적해를 저장하는 memo[ ]
- k가 입력으로 받은 매 Time t의 값
- 그래서 memo[ i ] = min또는max( memo[이전무언가] vs k )
-
아래 그림으로 이해를 해보자
- 이때 min( )비교를 하기 위해서 배열 안에 최적해값(=초기 개수)을 Infinity(=100001)로 둔다
- i = 각각의 화폐 단위를 가져옴
- j = 계산할 현재 금액
- if d[j - i] != 10001:
- (중요) 이전 금액을 봄 => (현재 금액 - 화폐단위 금액)계산한 금액이 있다면
''' python '''
#n, m = map(int,input().split())
#array = [input() for _ in range(n)]
n = 3
m = 7
array = [2, 3, 5]
# 배열의 index = 화폐, 배열[idx] = 계산된 돈
memo = [10001] * (m+1) # 각 인덱스에 해당하는 값은 INF(무한)으로 설정하는데, 이 문제에선 10,001을 사용
memo[0] = 0
# 다이나믹 프로그래밍
for i in array: # i = 각각의 화폐 단위를 가져옴
for j in range(i, m+1): # j = 계산할 현재 금액, "i부터 시작!!!"
# memo 풀스캔하면서 화폐로 계산 가능하면
if memo[j - i] != 10001: # (중요) 이전 금액을 봄 => (현재 금액 - 화폐단위 금액)계산한 금액이 있다면
memo[j] = min(memo[j], memo[j - i] + 1) # 이전 금액에 인덱스 위치의 값에 +1한 것과 비교
print(memo)
if memo[m] == 10001: # m원을 만들 방법이 없는 경우
print(-1)
else:
print(memo[m])
- 즉 얘는 해당 위치 앞에 있는 모든 애들을 브루트폴스로 확인함
- 확인해서 있으면 계산없이 갖다 씀(그래서 메모이제이션)
Do My Best