이 문제 말고 그냥 개념적인걸 설명해볼게요.
흔히 피보나치를 dp memoization의 예로 많이 드는데요
피보나치 수를 보면 n번째 피보나치 수는 n-1번째 피보나치 수와 n-2번째 피보나치 수의 합이잖아요.
그럼 n번째 피보나치 수를 f(n)이라 할때, f(n) = f(n-1) + f(n-2)이죠.
그런데 f(n-1)을 또 구해볼게요.
f(n-1) = f(n-2)+f(n-3)이죠.
여기서 보면 f(n)을 구하는데 f(n-2)를 구하죠?
그런데 f(n-1)을 구하는 데에도 f(n-2)를 구할 필요가 있어요.
즉, f(n)값을 구하려면 f(n-2)를 2번 가져다 써야 하는데, 이게 그냥 가져다 쓰는게 아니라 직접 구해야 된다는 문제가 있습니다.
그니까 f(n-2)는 그냥 뚝딱 나오는게 아니라 "계산"을 해야한다는 거죠.
그런데 f(n-2)라는 값을 한번 계산했다면, 그 값은 변하지 않습니다.
그럼 다음번에 f(n-2)를 호출했을때 그 값을 구하지 않고 이전에 구했던 값을 바로 가져다 쓰면 좋겠죠?
그래서 그 부분을 메모해 두는 거에요.
제가 말한 부분을 밑에 코드로 적어봤습니다. 주석만 읽어보시면 바로 알 수 있을거에요.
hyundo1226 7년 전 1
시간초과를 해결하기위하여 메모이제이션을 사용해야한다고 하는데
여기서 메모이제이션을 사용하면 왜 수행시간이 줄어드는지, 어떻게 구현해야하는지 잘모르겠습니다.
메모이제이션을 통해 그 순간의 값을 저장하여 중복계산을 하지 않는다는데 어떤식으로 돌아가는지도 알고싶습니다!