February 3, 2021 9:00 AM (GMT+9) February 5, 2021 9:00 AM (GMT+9) February 9, 2021 9:00 AM (GMT+9) February 23, 2021 9:00 AM (GMT+9)
동적계획법은 최적화 문제를 연구하는 수학이론에서 왔다.
분할 정복과 같은 접근 방식을 의미 → 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다.
둘의 차이점 - 문제를 나누는 방식
동적계획법 - 문제의 답을 한 번만 계산하고 계산 결과를 재활용할수있다. → 캐시 사용
분할 정복 - 각 문제들이 서로 연관이 없다. 즉 한 부분 문제를 한번만 해결한다.
중복되는 부분 문제 (overlapping subproblems) : 두 번 이상 계산되는 부분문제
캐시 (cache) : 이미 계산한 값을 저장해 두는 메모리의 장소
대표적인 예로 이항계수의 계산이있다.
${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}$
메모이제이션 : 함수의 결과를 저장하는 장소를 마련하고 한번 계산한 값을 저장해 뒀다가 재활용하는 최적화 기법
<aside> 📌 분할정복과 동적계획법은 접근방식이 같다. 둘의 차이점은 문제를 나누는 방식에 있다. 동적계획법은 문제가 중복된다. 따라서 메모이제이션기법을 사용하며 이때 캐시라는 장소를 이용한다.
</aside>