Dynamic Programming (동적 계획법)

Dynamic Programming (DP)

- 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법

- 나누어진 문제들은 중복 계산하지 않음 (계산 결과를 저장하여 중복 계산을 제거하는 것이 핵심)

- 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용

 

Memoization

- 계산한 결과를 배열에 저장

 

조건

1. Overlapping Subproblems : 문제를 부분 문제로 쪼개고 그 문제의 결과값을 재활용 

2. Optimal Substructure : 부분 문제의 최적 결과값을 사용해 문제의 최적 결과를 낼 수 있는 경우

f(1), f(2), f(3), ... 등이 여러번 다시 계산되고 있음

 

과정

1. 문제의 논리가 작은 논리의 합으로 구성되어 있는지 확인

2. 문제의 변수 파악

3. 변수 간 관계식 만들기 (점화식)

4. Memoization

5. 초기값 확인

6. 구현 (Top-Down, Bottom-Up)

 

vs Divide and Conquer (분할 정복)

- 분할 정복은 문제의 중복 계산이 이뤄지지 않음 -> 부분 문제를 재활용할 이유가 없음

 

vs Greedy

항상 최적해를 구해주지는 않지만, 특수한 경우에는 최적해를 구하는 것이 가능함

ex) A 지점에서 B 지점까지 가능한 빨리 이동하는 경로 구하기

- DP : 모든 상황과 교통 정체를 전부 감안하여 최적 경로 구함

- Greedy : 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색 -> 최적 경로를 보장하지 않음

 

 

 

 

출처

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

https://blog.naver.com/ndb796/221233570962

https://hongjw1938.tistory.com/47