[알고리즘]동적 계획법

동적계획법

정의

 큰 문제를 작은 문제로 나누서 푸는 알고리즘

분할정복과 방식은 같지만 분할정복은 계산한 부분을 한번만 쓰고 더이상

쓰지 않지만, 동적계획법은 메모이제이션을 이용하여 결과를 반복 사용한다

메모이제이션

-중복계산을 피하기 위해 계산 결과를 배열로 저장하여 필요할때 호출해서

사용하는 방법. 계산 중복을 피할 수 있어서 시간복잡도가 줄어듬

Top-Down

재귀와 같은 방식으로 위에서 아래로 내려오는 방식

함수 호출을 줄이기 위해, 메모이제이션을 사용함

Bottom-up

Top-Down 방식과 달리 for문을 이용해 처음값부터 다음값을 계산해 나가는 방식

---

동적계획법의 이용

동적계획법 알고리즘은 최적값을 구할 때 주로 사용한다

(1)문제를 작은 단위로 나눈다

(2)가장 작은 부분 문제를 푼 후 값을 저장한다->메모이제이션

(3)메모이제이션된 부분 문제들의 해를 이용해 상위 문제의 답을 구한다.

(4)3번 과정을 최종문제의 답이 나올때까지 반복한다.