[알고리즘] Dynamic Programming(동적 계획법)

1.  동적 계획법(DP)란?

- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산X

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

2.  DP vs 분할 정복

DP	분할 정복
각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨	동일한 부분 문제가 반복적으로 계산되지 X
최적 부분 구조를 가질 때 사용 O (큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황)

3.  DP의 2가지 방식

1. Top-Down(하향식)

- 재귀 이용

- 메모이제이션 기법 활용

<메모이제이션(Memoization)>
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법(캐싱)
- 다이나믹 프로그래밍 구현 기법(하향식)이지만 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있음(큰 개념임)

 

2. Bottom-Up(상향식)

- 반복문 이용

- 다이나믹 프로그래밍의 전형적인 형태
- 결과 저장용 리스트: DP 테이블

4. DP 사용 조건

1. 최적 부분 구조
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결O
2. 중복되는 부분 문제
- 동일한 작은문제를 반복적으로 해결해야 함

 

<다이나믹 프로그래밍 문제에 접근하는 방법>
- 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요!
- 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한 후 다이나믹 프로그래밍 고려
- 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 후 작은 문제에서 구한 답이 큰 문제에 그대로 사용된다면 메모이제션을 활용해 코드 개선
- 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음