다이나믹 프로그래밍

다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법

• 이미 계산된 결과는 별도의 메모리에 저장하여 다시 계산하지 않도록 한다.
• 구현은 탑다운, 바텀업으로 구성된다.

동적할당과 상관없음 그냥 의미 없음

다음과 같은 문제일 때 사용
1. 최적 부분 구조

• 큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 탑을 모아서 큰 문제를 해결할 수 있을 때
  2 중복되는 부분 문제
• 동일한 작은 문제를 반복적으로 해결할 때
  
  이런식으로 해결해야 하는 문제가(f(n)) 작은 문제로 해결될 수 있을 때

메모제이션

한번 계산한 결과를 메모리 공간에 메모하는 기법, 캐싱이라고도 불림
탑다운 방식에서 쓰임 이 때 결과 저장용 리스트를 DP테이블이라고 부름

탑다운 방식의 피보나치 수열

바텀업 방식의 피보나치 수열

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토 후 다이나믹 프로그래밍을 고려한다. 중복되는 계산이 많아져(완전탐색등) 시간복잡도 때문에 시간초과가 날 때