다이나믹 프로그래밍 dp
메모리를 적절히 사용하여 수행 사긴 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과는 별도의 메모리 영역에 저장하였다가 같은 계산을 다시 하지 않도록 한다
일반적으로 탑다운과 보텀업으로 나뉜다
동적 계획법이라고도 부른다
두가지 조건을 만족하면 사용한다
1. 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결 가능하다
2. 중복되는 부분 문제(Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결하는 문제
대표적인 문제
피보나치 수열
메모이제이션(Memoization)
한 번 계산한 결과를 메모리 공간에 메모하는 기법
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다
메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념의 의미
다이나믹 프로그래밍에 국한된 개념이 아니다
결과를 담아놓기만하고 다이나믹 프로그램밍을 위해 활용하지 않을 수도 있다
d = [0]* 100 # 0~ 99번째
보텀업
밑에서 부터
업데이트된다
