[알고리즘] 다이나믹 프로그래밍

https://www.youtube.com/watch?v=5Lu34WIx2Us

🌟이것이 코딩 테스트다 / 나동빈 dp

다이나믹 프로그래밍

• 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간을 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
• 다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식 (탑다운 바텀업)으로 구성됨
• 다이나믹 프로그래밍은 동적 계획법이라고 부른다.
• 자료구조에서 동적 할당(dynamic alocation)은 프로그래밍이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다
  • but, 다이나믹 프로그래밍에서 다이나믹은 별 의미 없이 사용된다.

다이나믹 프로그래밍 조건

• 최적 부분 구조
• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 (하향식 최대값)
• 중복되는 부분 문제
• 동일한 작은 문제를 반복적으로 해결해야함(피보나치)   

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

🌟10분이면 DP 동적 계획 완전 이해 개발자로 취직하기 (개발자로 살아남기)

다이나믹 프로그래밍은 완전탐색 DFS, BFS와 같이 수많은 경우의 수를 따져야 하는데 그 경우의 수가 너무 많아 속도가 느려지는 문제를 개선하고자 할 때 사용합니다
(프로그래머스 정수 삼각형)
메모리를 사용해서 중복연산을 줄이고 중복 연산을 줄여서 수행속도를 개선한다
한 교수는 기억하기 알고리즘, 기억하며 풀기라고 부른다 

Dp 구분하는 방법
1.   DFS/BFS로 풀수있지만 경우의 수가 너무 많은 경우
2.   경우의 수에 중복 연산이 많은 경우