동적 계획법이란?

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘
• 중복 계산을 줄여서 계산 속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다.
• 일반적으로, 재귀적으로 구현되며 메모이제이션 기법을 사용하여 중복 계산을 피한다.

동적 계획법의 구현 단계

1. 문제를 하위 문제로 쪼갠다.
2. 하위 문제를 재귀적으로 해결한다.
3. 결과를 저장한다. → 메모이제이션
4. 저장된 결과를 이용하여 큰 문제를 해결한다.

동적 계획법의 메모이제이션

• 메모이제이션 : 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복 계산을 피함으로써 성능을 높일 수 있다.

• 메모이제이션 구성 과정

1. 입력 값에 대한 결과 값을 저장할 메모이제이션 테이블을 초기화한다.
2. 함수를 호출할 때, 먼저 메모이제이션 테이블에서 해당 입력값의 결과값이 이미 저장되어 있는지 확인한다.
3. 저장되어 있으면 해당 결과값을 반환하고, 저장되어 있지 않으면 계산을 수행하고 그 결과를 메모이제이션 테이블에 저장한다.

• 메모이제이션 테이블이란?