👩🏼‍💻TIL : 12. 다이나믹 프로그래밍

00. 다이나믹 프로그래밍이란?

   동적계획법이라고도 부른다.

 

01. 일반적인 프로그래밍 분야에서의 동적이란 어떤의미일까?

  - 자료구조에서 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'

  - 반면에 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용된 단어

 

02. 다이나믹 프로그래밍의 조건

(1) 최적 부분구조 (Optimal Substructure)

 - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

 - 분할정복과 다른점 : 전의 값이 재사용 전의 값을 계산한것을 다시 쓰는게 아니ㅏ 각 각 판별하고, DP 

 

(2) 중복되는 부분문제 (Overlapping Subproblem)

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