동적 프로그래밍이란?

• 동적 프로그래밍은 복잡한 문제를 작은 하위 문제들로 나누어 푸는 최적화기법 DFS 알고리즘은 동적프로그밍 기법으로 문제를 해결할 수 있다.

• 동적 프로그래밍은(병합/퀵 정렬 알고리즘에서 사용했던) 분할/정복과는 전혀 다른 접근 방식이다.

  • 분할/정복
  • 문제를 독립적인(independent) 하위 문제들로 분할하고 다시 합치는 해결 방식
  • 동적 프로그래밍
  • 종속적인(dependent)하위 문제들로 나눠 해결한다.
  • 이 얘기는 재귀호출로 스택을 쌓아서 각 스택별로 process를 처리하면서 각 스택의 return 값을 다음 스택(호출한 함수 프로세스)으로 넘겨서 문제를 해결하는 형식 같다.

동적 프로그래밍을 사용해 문제를 해결할 때 중요한 세단계

1. 하위 문제들을 정의한다.
2. 하위 문제들을 풀기위한 '재귀를 구현'한다.
3. 베이스 케이스를 찾아낸다.^basecase

동적 프로그래밍 방식으로 해결한 유명한 알고리즘 문제들

1. 배낭문제

   • 짐 무게의 최댓값이 정해져 '배낭'에 일정가치와 무게의 집들을 넣을 때 가지츼 총합을 최대로 할 방법

2. 최장공통부분수열(LCS, longest common subsequence)

   • 다수의 수열 모두의 부분수열이 되는 수열 중에 가장 긴 것(남아 있는 원소의 순서를 바꾸지 않은 채 일부 원소를 삭제하든지 하여 다른 수열로부터 파생 가능한 수열)을 찾는 문제

3. 행렬 연쇄 곱셈(matrix chain multiplication)

   • 행렬 집합에서 가장 효율적(가장 적은 연산)으로 행렬들을 곱하는 곱셈 순서 조합을 찾는 것

4. 동전 교환

   • 정해진 금액을 동전(d1, d2, d3, ... dn)으로 바궈주는 경우의 수

참고

자바스크립트 자료 구조와 알고리즘 - 에이콘