[알고리즘] 동적 계획법 (dynanmic programming)

다이나믹 프로그래밍

하나의 문제는 한 번만 계산하는 알고리즘으로 큰 문제를 작은 문제로 나누어 푸는 알고리즘

 

다이나믹 프로그래밍을 사용하기 위한 조건

-작은 문제로 나눌 수 있을 때

-작은 문제의 답이 그것을 포함하며 더 큰 문제에서도 답이 동일하게 나올 때

 

다이나믹 프로그래밍 원리

메모이제이션을 활용해 작은 문제에서 계산한 결과 값을 배열에 저장해두고

나중에 큰 문제에서 그 값이 다시 필요할 때 동일한 계산을 진행하지 않고 저장된 값을 반환받아서 계산

+메모이제이션

결과를 저장해 함수가 한 번만 실행되는 것을 보장하는 기술

동적계획법을 쓸 때 많이 사용한다.

 

다이나믹 프로그래밍 구현법

1. 탑-다운

재귀함수로 구현할 때 대부분 탑-다운 방식을 사용하며 큰 문제를 풀 때

작은 문제 값이 없다면 그 때 작은 문제의 값을 계산함.

2. 다운-탑

작은 문제부터 먼저 계산하여 큰 문제의 값을 계산함.

 

다이나믹 프로그래밍 점화식 찾는 법

1. 작은 문제들의 값(0,1,2,3,3)들을 직접 계산해보면 점화식이 보임

그 점화식을 활용해 다이나믹 프로그래밍을 구현하면 됨.

2. 이전 단계에서 다음 단계로 가는 가짓수가 정해져있다면 그걸 이용해도 됨

   ex. 도형을 쪼갤 때 특정한 규칙으로만 쪼개져서 n-2단계/n-1단계에서 n이 되는

        가짓수가 정해져있을 경우

 

분할 정복 vs 다이나믹 프로그래밍

분할 정복은 단순히 큰 문제를 작은 문제로 나누어 푸는 것으로 작은 문제의 답이 항상

큰 문제의 답이 되지 않아 작은 문제를 여러 번 반복적으로 계산해야 함.

반면에 다이나믹 프로그래밍은 작은 문제 계산을 중복적으로 하지 않고 작은 문제의 답이

큰 문제에서도 변하지 않음을 이용함

 

 

 

참고 사이트

https://blog.naver.com/ndb796/221233570962

https://galid1.tistory.com/507