memoization
-
[Java] 동적 계획법 (DP: Dynamic programmig) 이해하기 <적용문제>JAVA 2024. 4. 3. 14:06
1. 동적 계획법이란? 동적 계획법(Dynamic programming)은 중복 계산을 줄이기 위해 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘을 말한다. 해당 알고리즘의 특징은 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피하고, 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다. 일반적으로 재귀적으로 구현된다. 메모이제이션(Memoization) 이란? 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 속도를 빠르게 하는 방법이다. 동적 계획법 알고리즘을 구현할때 다음과 같은 단계를 따른다. 1. 문제를 하위 문제로 쪼갠다. 2. 하위 문제를 재귀적으로 해결한다. 3. 결과를 저장한다. (메모이제이션) 4. 저장된 결과를 이용하여 큰 문..