다이나믹 프로그래밍
다음의 조건을 만족할 때 사용
- 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다
- 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 합니다.
피보나치 수열
예를들어, 피보나치 수열을 재귀로 사용하면 f(2)가 반복적으로 호출됨.
-> 시간복잡도 개선이 필요함!
피보나치 수열은 다이나믹 프로그래밍의 조건에 모두 만족하므로 DP로 구현!
구현 방법
- 탑다운(하향식) : 재귀 이용. 작은 문제들을 재귀적으로 호출해서 큰 문제 해결. 한번 계산한거 메모이제이션
- 보텀업(상향식) : 아래쪽부터 계산한 값을 이용해서 위에거 해결. 반복문 이용. <<<전형적인 디피 형태>>>
- 메모이제이션 Memoization : 한번 계산한 결과를 메모리 공간에 저장해둠. == 캐싱 : 값을 기록해놓는다
- 결과 저장용 리스트는 DP 테이블이라고 부른다.
- 탑다운
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))- 보텀업 ⭐️
d = [0] * 100 # 앞서 계산한 결과 저장하기 위한 dp 테이블
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])메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N) !
분할정복과의 차이는?
둘다 최적 부분구조를 가질때 사용함. 하지만, 차이점은 "부분 문제의 중복"이다. dp문제는 각 부분 문제들이 서로 영향을 미치며 부분문제가 중복됨! 하지만 분할 정복 문제는 동일한 부분문제가 중복되지 않음.
(ex)한번 분할 이후에 해당 피벗을 다시 처리하지 않음.
BOJ_2839 설탕배달
https://www.acmicpc.net/problem/2839
n = int(input()) dpt = [1667]*(n+1) ## 초기화 주의! dpt[0] = 0 for i in [5,3]: for j in range(3,n+1): if dpt[j - i] != 1667: dpt[j] = min(dpt[j], dpt[j-i] +1) print(dpt[-1] if dpt[-1] != 1667 else -1)
dpt배열 : 킬로그램에 대해 최대로 배달할 봉지수인 1667로 초기화를 하고 0은 없으므로 0처리한다.
입력 조건에 의해 N은 3이상이다 !
3이상 각 킬로그램에 대해 현재 저장된 dpt값과 5(3)킬로그램 작은 킬로그램에 대한 dpt값+1 중 최소를 구하여 갱신한다.
예를들어 6이면,
i=5일때 min(dpt[6], dpt[1] +1)인데 (min(1667,1668))이므로 1667
i=3일때 min(dpt[6], dpt[3] +1)이고, dpt[3] = min(dpt[3], dpt[0] +1)=min(1667,1)이므로 1이어서
min(1667, 2)이므로 2로 갱신된다.
-> 큰 문제에 대한 답이 작은 문제들의 답으로 모아 해결할 수 있다는 것이 이런것 !!
if dpt[j - i] != 1667: 가 의미하는것은,
(i= 5 or 3)이므로 5나3의 한봉지 전 킬로그램에 대해 최소갯수를 구해놨다는 것.
