[알고리즘 문제 해결 전략] 동적 계획법

soyena729·2020년 6월 30일
0

중복되는 부분 문제

  • 어떤 부분 문제는 2개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 것이 아니라 한 번만 계산하고 그 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있음
  • 이미 계산한 값을 저장해두는 메모리의 장소를 캐시(cache)라고 부름

메모이제이션

  • 함수의 결과를 저장하는 장소를 마련해두고 한 번 계산한 값을 저장해뒀다 계속 재활용하는 최적화 기법을 메모이제이션(memoization)이라고 함
  • 메모이제이션을 사용하면 모든 문제가 한 번만 계산된다고 보장할 수 있기 때문에 함수 호출이 매우 감소
profile
나는 나다!

0개의 댓글