1. 언제 사용되는가?

1-1. 최적 부분 구조

큰 문제를 작은 문제로 나누어 작은 문제의 답을 모아 큰 문제를 해결

1-2. 중복되는 부분 문제

동일한 작은 문제를 반복적으로 해결해야 할 때

1-3. 대표예시

피보나치 수열

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

점화식 사용

:인접한 항들 사이의 관계식 사용

f(100)을 하면..엄청난 계산량 때문에 해결할 수 없음..

즉, 중복 문제 발생!!

단순 재귀함수로 해결하면 시간 복잡도 O(2^N) 를 가지게 됨

2. 그렇다면 다이나믹 프로그래밍을 사용해보면??

2-1. TOP Down(하향식) - 메모이제이션(Memoization)

한 번 계산한 결과를 메모리 공간에 메모

-가은 문제를 다시 호출하면 메모했던 결과 그대로 가져옴

-값을 기록해 놓는다는 점에서 캐싱(Caching)이라고 한다.

단, 이 개념은 다이나믹 프로그래밍에 국한된 개념이 아니다!

왜냐 결과만 담아놓고 다이나믹 프로그래밍을 위해 활용되지 않을 수 도 있으니까..

< Top Down -재귀함수 이용 >

복잡도 : O(N)

선형 시간 알고리즘으로 피보나치 해결 가능!

2-2. Bottom up (상향식)

--> 결과 저장용 리스트는 "DP 테이블"라고 부름 (파이썬 외 다른 언어는 배열)

3. 다이나믹 프로그래밍 VS. 분할 정복

●공통점 : 작게 나눌 수 있다

-최적 부분 구조를 가질 때 사용 가능

-큰 문제를 작은 문제로 나눌 수 있음

-작은 문제의 답을 모아 큰 문제 해결 가능

●차이점 : 부분 문제의 중복

-다이나믹에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복

-분할 정복은 동일한 부분 문제가 반복 계산되지 않음

3-1. 다이나믹 프로그래밍에 쉽게 접근하려면?

step1. 그리디, 구현, 완전 탐색 등의 아이디어로 문제 해결 가능한가?

step2. 다른 알고리즘이 떠오르지 않으면 다이나믹 프로그래밍

step3. 재귀함수로 비효율적인 완전 탐색 프로그램 작성

step4. Top Down- 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법으로 사용!

일반 코테는 기본 유형의 다이나믹 프로그래밍 출제!

참고한 인강
인강 : 유튜브 동빈나 이것이 코딩테스트다 6.다이내믹 프로그래밍
https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6