DP (1) 썸네일형 리스트형 24. Dynamic Programming & Memoization 재귀를 설명한 글의 끝부분에서 입력값이 조금만 커져도 재귀호출 횟수가 급격하게 늘어나는 문제점에 대해서 언급했는데, 이렇게 되는 이유는 중복되는 부분 문제를 계산하는 횟수가 너무 많기 때문이다. 이 문제를 풀어 보면 알 수 있지만 피보나치 수를 구하기 위해서 이 글에 나온 것처럼 코드를 짜면 함수 호출의 횟수 자체가 피보나치 수만큼 증가하기 때문에 이렇게 해서는 빠른 코드를 짤 수 없다. 하지만 중복되는 부분 문제를 살펴보면 중복되는 부분 문제에 대한 답이 항상 같기 때문에, 만약 어떤 부분 문제의 답을 계산했다면 그 계산 결과를 저장한 뒤 나중에 같은 부분 문제를 풀 때 기존에 계산한 답을 사용하면 되므로 성능을 크게 향상시킬 수 있다. 이러한 방법을 메모이제이션(Memoization)이라고 한다. (.. 이전 1 다음
