다이나믹 프로그래밍 (DP) - 동적 계획법

다이나믹 프로그래밍(DP)

메모리(배열, 자료구조를 만들어서 사용)를 적극 활용해 수행 속도를 비약적으로 줄이는 기법

  메모리제이션(Memorization)

• 계산한 결과를 메모리 공간에 기억
• 같은 문제를 다시 호출 ⏩ 결과를 그대로 가져옴
• 값을 기록 == 캐싱

 DP 조건

 예시) 피보나치 수열 (점화식을 이용한 수열)

 1. 최적 부분 구조

  - 큰 문제 ▶ 작은 문제 ⏩ 작은 문제들을 모아서 큰 문제 해결

 2. 중복되는 부분 문제 

 - 작은 문제들이 반복되어야 한다.

 

탑 다운(하향식)

• 재귀를 이용

바텀 업(상향식)

• 반복문을 이용

분할 정복과의 차이점 = 부분 문제의 중복 여부

• DP와 분할 정복은 모두 최적 부분 구조를 가질 때 사용! ( 큰 문제 ⏩ 작은 문제 )
•  DP는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복
• 분할 정복은 동일 부분 문제의 반복 ❌
  • ex) 트리 구조 ⏩ 하위 트리들이 합쳐져서 상위 트리 🔜 DP

코딩테스트에서 단번에 DP 유형 파악하기

1. DFS/BFS로 풀 수는 있지만, 경우의 수가 너무 많은 문제 
2. 경우의 수들에 중복적인 연산이 많은 문제

공부방법

• 오래 붙잡지 말기. 30분정도만 고민하기.
  많이 경험하는 수밖에없다. DP 사고방식을 습득해야함
• 현재 단계까지의 연산 정보들을 어떻게 남겨둘지 집중
• 어떻게 누적시킬지도 고민

참고:

https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 

https://www.youtube.com/watch?v=0bqfTzpWySY