hyundo1226   7년 전

시간초과를 해결하기위하여 메모이제이션을 사용해야한다고 하는데

여기서 메모이제이션을 사용하면 왜 수행시간이 줄어드는지, 어떻게 구현해야하는지 잘모르겠습니다.

메모이제이션을 통해 그 순간의 값을 저장하여 중복계산을 하지 않는다는데 어떤식으로 돌아가는지도 알고싶습니다!

plzrun   7년 전

이 문제 말고 그냥 개념적인걸 설명해볼게요.


흔히 피보나치를 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)를 호출했을때 그 값을 구하지 않고 이전에 구했던 값을 바로 가져다 쓰면 좋겠죠?

그래서 그 부분을 메모해 두는 거에요.



제가 말한 부분을 밑에 코드로 적어봤습니다. 주석만 읽어보시면 바로 알 수 있을거에요.


sksdong1   7년 전

이 문제에서는 

임의의 위치 a,b에 도달했다고 가정할게요

(0,0) 에서 (a,b)로 어떤 경로를 통해서 왔던 a,b에서 끝점으로 가는 경우에는 변함이 없습니다.

따라서 dp를 사용해서 (0,0) ->(a,b) -> (N,M) 으로 갈 때

(0,0)->(a,b)의 경우의 수 만큼 (a,b)->(N,M) 경로를 똑같은걸 또 만드는 것을 방지하기 위해 dp를 사용합니다

댓글을 작성하려면 로그인해야 합니다.