Dynamic Programming

Dynamic Programming

Dynamic Programming 즉, DP 문제는 이전항과의 관계를 찾아 이를 다음 항의 연산과정에서 활용한다. 그러기 위해 점화식을 세워 이전항과 구해야할 항의 관계를 파악해야한다. 또한,중복연산을 줄이는 것이 중요하다. 값이 커질 수록 중복연산으로 인한 시간 초과 문제가 발생하기 때문에, DP에서는 이러한 문제를 해결하기 위해 중간 연산 결과를 저장하는 Memoization 기법을 활용한다.

Fibonacci Function을 이용해서 아래 두가지 방식의 차이점을 알아보자

피보나치 수열의 점화식은 다음과 같다 F_n=F_n-1+F_n-2

Top-Down

탑다운 방식의 설계의 경우 큰 문제를 해결하기 작은 문제를 호출하는 방식을 의미한다. 재귀적 호출을 통해 큰 수를 잘게 쪼개 중간 연산결과값이 있을 때까지 분할을 수행한 후, 이후에 이를 통합한다.

d=[0]*100

def fibo(x):
  if x==0 or x==1:
    return 1
  if d[x]!=0:
    return d[x]
  d[x]=fibo(x-1)+fibo(x-2)
  return d[x]

fibo(10)

Buttom-Up

반면 바텀업 방식은 밑에서 부터 계산하는 방식으로, 처음부터 연산을 수행해 끝까지 이어나가는 방식이다.

d=[0]*100

def fibo(x):
  d[1]=1

  for i in range(2,x):
    d[i]=d[i-1]+d[i-2]

  return d[i]
fibo(10)

0/1 knapsack

무게 제한이 있는 가방이 있고, 무게와 가치가 정해진 물품들이 있을 때, 가방 안에 물품을 넣는데 이때, 가방 안에 들어갈 수 있는 물품의 최대 가치의 값을 구하는 유형이다.

이를 구하기 위해서는 각각의 물품에 대해 물품을 넣었을때 와 넣지 않았을때의 무게와 가치를 비교해서 넣을 지 말지를 정하는 문제이다.

아래의 예시를 통해 알아보자 최대 무게가 7인 가방이 존재한다. 이때 물품의 종류는 무게: (3,4,2,4), 가치: (10,9,9,7)이다

아래와 같은 배열(arr)이 있다고 가정하자 | |1|2|3|4|5|6|7| |–|–|–|–|–|–|–|–| |0|0|0|0|0|0|0|0| |1번 item 고려|0|||| |2번 item 고려|0|||| |3번 item 고려|0|||| |4번 item 고려|0||||

1번 item을 봤을때, 무게가 3이고, 가치는 10이다. 해당 물건을 넣지 않을 경우와 넣었을 때의 가치를 비교해야한다.

무게 1~2가 남았을 때는 넣지 못하므로 arr(0,무게)으로 각각 초기화되고,

무게 3이상일때는 넣지 않은 경우 arr(0,무게)와 넣었을 경우arr(0,무게-3)+10 를 비교하여 무게 3 이상 남았을때는 무조건 넣는 것이 이득이다.

	1	2	3	4	5	6	7
1번 item 고려	0	0	10	10	10	10	10
2번 item 고려	0
3번 item 고려	0
4번 item 고려	0

2번 item을 봤을때, 무게가 4이고, 가치는 9이다. 해당 물건을 넣지 않을 경우와 넣었을 때의 가치를 비교해야한다. 즉, 넣지 않은 경우의 경우 arr(1,무게)와 넣었을 경우arr(1,무게-4)+9 를 비교한다

	1	2	3	4	5	6	7
1번 item 고려	0	0	10	10	10	10	10
2번 item 고려	0	0	10	10	10	10	19
3번 item 고려	0
4번 item 고려	0

3번 item을 봤을때, 무게가 2이고, 가치는 9이다. 해당 물건을 넣지 않을 경우와 넣었을 때의 가치를 비교해야한다. 즉, 넣지 않은 경우의 경우 arr(1,무게)와 넣었을 경우arr(1,무게-2)+9 를 비교한다

	1	2	3	4	5	6	7
1번 item 고려	0	0	10	10	10	10	10
2번 item 고려	0	0	10	10	10	10	10
3번 item 고려	0	9	10	10	19	19	19
4번 item 고려	0

4번 item을 봤을때, 무게가 4이고, 가치는 7이다. 해당 물건을 넣지 않을 경우와 넣었을 때의 가치를 비교해야한다. 즉, 넣지 않은 경우의 경우 arr(1,무게)와 넣었을 경우arr(1,무게-2)+9 를 비교한다

	1	2	3	4	5	6	7
1번 item 고려	0	0	10	10	10	10	10
2번 item 고려	0	0	10	10	10	10	10
3번 item 고려	0	9	10	10	19	19	19
4번 item 고려	0	9	10	10	19	19	19

이를 통해 최대 가치는 19임을 확인할 수 있다.

Algorithm

if weight[i] <= weight:
  dp[i][weight[i]]=max(dp[i-1][weight[i]],dp[i-1][weight-weight[i]]+price[i])
else:
  dp[i][weight[i]]=dp[i-1][weight[i]]

Question Types

Dynamic Programming은 대표적인 알고리즘이 구체적으로 나와 있지 않다. 문제에 따라서 입력,제한 조건에 맞춰 점화식을 세우고 이를 프로그래밍 해야한다.