동적 계획법

동적 계획법

동적 계획법이란

• 동적 계획법

  • 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방식

• 캐시

  • 이미 계산한 값을 저장해 두는 메모리의 장소

• 메모이제이션

  • 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법

  • 메모이제이션을 적용할 수 있는 경우

    • 함수의 반환 값이 시간, 프로그램 흐름의 영향을 받지 않고 입력 값만으로 결정되는 경우, 즉 참조적 투명성이 보장되는 경우.

    • 메모이제이션 구현 패턴

        int cache[1001][1001];
      
        int dp(int a, int b){
            // 기저 사례를 처리한다
      
            // (a, b)에 대해 미리 구해놓은 값이 있다면 그 값을 반환
      
            // 하위 문제 dp 계산
        }
      
        int main() {
            memset(cache, -1, sizeof(cache));
      
            // dp 호출
        }

출처