Dynamic Programming Algorithm

😼 구현 방법

1. 문제를 해결할 수 있는 재귀 관계식을 구한다.

2. 가장 작은 입력사례로부터 상향식 방법으로 문제 해결.

 

 

🐸 상향식과 하향식

• 상향식 접근은 재귀를 사용하지 않는다. 부분 문제를 해결한 후 table에 저장한다. table에 저장된 값을 이용해서 계산해나간다.
• 하향식 접근은 재귀를 사용한다.

 

🐣 동적계획법은 문제를 작게 나누고 상향식 방법으로 점차 큰 문제 해결.

오버헤드 발생이 없다.(재귀호출과 비교했을 때 장점)

재귀호출은 내부 시스템 호출 Stack을 사용하는 오버헤드가 발생하기 때문.

 

 

★ 분할정복과 동적계획법 비교

- 문제를 작은 사례로 분할하여 해결한다는 점은 동일

- 분할정복은 재귀 호출을 통해 분할하여 정복(Top-Down)

- 동적계획은 메모이제이션을 통해 상향식으로 정복(Bottom-Up)

 

 

동적 계획법은

1. Optimal Substructure : 큰 문제의 최적 솔루션에 작은 문제의 초적 솔루션이 포함됨

2. Overlapping Recursive Calls : 재귀호출이 심하게 중복되는 경우일 때 사용한다.

 

 

🐝 배낭 문제

w_i>w :

P[i, w]=P[i-1, w]

i이전 번호 물건의 가치를 대입

 

w_i<=w :

P[i, w]=max(v_i+P[i-1, w-w_i], P[i-1, w]) 

max(i번 물건의 가치 + P[i번 이전 물건 번호, i번 물건을 담고 난 후 남은 무게], 이전 번호 물건의 가치)

 

👇 배낭 문제와 관련 문제

1. 백준 1535. 안녕

 

 

 

참고 👇

SW expert academy

 

https://gsmesie692.tistory.com/113?category=523232 

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

 

https://www.hanbit.co.kr/media/channel/view.html?cms_code=CMS4008657032 

다이내믹 프로그래밍(Dynamic Programming)이란?