[알고리즘] 동적 계획법 (Dynamic Programming)

동적계획법

개념

복잡한 문제를 더 작은 하위 문제들로 나누어 푸는 알고리즘 기법이다. 하위 문제들의 결과를 저장하여 나중에 동일한 문제가 발생할 때 재사용함으로써 연산량을 줄일 수 있다. Top-down 방식과 Botton-up 두 가지 방식이 있다.

Top-down 방식

큰 문제에서 작은 문제로 접근하는 방식. 보통 재귀를 사용하며 메모이제이션 기법을 활용한다. *메모이제이션: 하위 문제의 결과를 캐시(저장)하여 동일한 하위 문제를 다시 계산할 필요가 없게 만드는 기법. 필요한 부분 문제들만 구한다. 재귀로 풀기 때문에 재귀의 장점인 점화식을 그대로 사용할 수 있다.

Botton-up 방식

작은 문제에서 큰 문제로 접근하는 방식. 보통 반복문을 사용하며 타뷸레이션 기법을 활용한다. *타뷸레이션: 하위 문제의 결과를 표에 저장하고, 이를 사용해 점진적으로 더 큰 문제를 해결하는 기법. 모든 부분 문제를 구한다.