다이나믹 프로그래밍은 정확히 말하면, 특정한 알고리즘은 아니다.
divide-and-donquer 와 같이 하나의 테크닉으로 보는 게 더 정확하다.
주로 최적화 문제에 사용하며 최대, 최소와 같은 optimal 값을 찾는 방법을 찾을때 사용한다.
하나의 큰 문제를 작은 subproblem들로 나누어서 푸는 방법인데, divide-and-donquer와 다른 점은 다이나믹 프로그래밍은 subproblem들이 서로 겹치는 부분이 있는, 그러니까 subproblem들이 같은 subproblem들을 공유한다는 것이다. (분할 정복은 subproblem들이 서로소이다.)
교수님께서 왜 이 방법이 "dynamic" 프로그래밍인가 말씀해주실 때, 거기엔 어른의 사정(...)이 관련되어 있다고 하셨던 기억이 있다. 그러니까 중요한 건 다이나믹이 아니란 점.
쉽게 생각하면, 다이나믹 프로그래밍은 "tabular" 즉, 계속해서 나오는 값들을 저장할 테이블을 만들어서 값을 기억해두었다가 사용하는 방법이다. (memoization)
11053: 가장 긴 증가하는 부분 수열
n = int(input())
a = list(map(int, input().split()))
memo = [1] * n
for i in range(n):
for j in range(i):
if a[i] > a[j]:
memo[i] = max(memo[i], memo[j]+1)
print(max(memo))다이나믹 프로그래밍은 기본적으로 공간을 통해 시간을 절약하는 방법이다.
그래서 대부분 메모리를 크게 갖는 배열을 하나 할당하고 시작한다. (여기서는 memo)
for 문을 통해 i 번째 원소보다 앞에 있고 크기가 작은 원소들에 대해 어떤 수열이 더 긴지 비교하게 된다.
2156: 포도주 시식
n = int(input())
w =[]
for i in range(n):
w.append(int(input()))
memo = []
memo.append(w[0])
if(n > 1):
memo.append(w[0] + w[1])
if(n > 2):
memo.append(max(memo[0]+w[2], w[1]+w[2], memo[1]))
for i in range(3, n):
memo.append(max(memo[i-2]+w[i], memo[i-3]+w[i-1]+w[i], memo[i-1]))
# (전전 최대 + 현재 와인) or (전전전최대 + 전 와인 + 현재 와인) or (전 최대 + 현재 와인 안마심)
print(m[n-1])포도주 양에 대한 입력받을 때 모두 줄바꿈이 이루어져서 편의를 위해 for 문을 사용했다.
피보나치 수와 같이 앞의 값 3개는 매뉴얼하게 할당해주었다.
if 문 없이 append하게 되면 포도주 잔이 부족해서 w에 값이 없을 경우 IndexError가 생길 수 있다.
그 후엔
- 2번째 전의 와인까지의 최댓값 + 지금의 와인을 마심
- 3번째 전의 와인까지의 최댓값 + 바로 전 와인, 지금의 와인을 마심
- 바로 전 와인까지의 최댓값, 지금의 와인은 마시지 않음
세 가지 경우 중 가장 많은 포도주를 마시는 방법을 찾아서 저장한다.
note
어떤 문제(주로 최대 최소를 찾는)가 작은 문제들의 반복으로 이루어져 있으면,
테이블의 값들을 "어떻게 채워나갈지" 를 찾아 그 문제를 쉽게 해결할 수 있다.
