sotter1020   2년 전

코드는 생각보다 간단하게 나왔는데..

반례가 무엇이 있을까요?

target노드에서 start노드까지 거꾸로 가는 식입니다.

간략하게 주석을 달아 놓았습니다.

djm03178   2년 전

여러 가지 틀린 점이 있습니다. 다음들을 고치면 맞습니다.

  1. cache, g, spend는 모두 크기가 1001이므로, 원소는 0번부터 1000번까지 있습니다. 그러니 초기화도 0번부터 1000번까지만 이루어져야 하고, 1001번은 건드리면 안 됩니다.
  2. previousWeight는 필요하지 않습니다. 오히려 이 변수의 존재 때문에 문제가 됩니다. previousWeight는 같은 here에 대해 time 함수가 호출될 때마다 변할 수 있고, 그 말은 cache[here] 역시 매번 변할 수 있어야 한다는 뜻인데, 그러면 메모이제이션의 의미가 없어집니다. previousWeight를 아예 없애고, time 함수의 의미를 이렇게 정의해서 생각해 보세요. "here번째 건물을 짓기까지 걸리는 최소 시간을 반환하는 함수"
  3. 어떤 건물을 짓기까지 필요한 최소 시간이 0일 수도 있습니다. 그러면 cache[here]는 0으로 계산이 됨에도 불구하고, 나중에 time(here)가 다시 호출되었을 때 17번째 줄에 걸리지 않고 또 재계산하게 됩니다. 이것이 재귀적으로 반복되면 지수 복잡도가 될 수 있어 시간 초과가 납니다. 재귀 메모이제이션에서 매우 중요한 것 중 하나는, 초기값은 절대로 계산 결과값이 될 수 없는 값 (-1 등)으로 지정해야 한다는 것입니다.

sotter1020   2년 전

1번은 컴파일에러가 안난게 신기하네요.. 부끄러운 실수를 했습니다.. 3번도 하하하가 나올 만한 실수 인거 같네요!

2번이 잘 이해가 안되서요! previousWeight를 없애고 계산하면 탐욕법이 되는거 아닌가요?

지금 무엇을 말씀하시는지 알았는데..
머리에서 딱 어떻게 고쳐야겠다라는 생각이 안들어서요!
조금만 더 구체적으로 설명해주시면 감사합니다!





djm03178   2년 전

다이나믹 프로그래밍을 하는 데에 중요한 것 중 하나는, 큰 문제를 한 번에 해결하려 하지 말고 부분 답을 하나씩 구해나가는 것입니다. 그 부분 답을 구하기 위해 필요한 점화식만 잘 세우면 됩니다.

time(here)를 "here번째 건물을 짓기까지 걸리는 최소 시간을 반환하는 함수"라고 정의해봅시다. 그러면 time(here)의 값을 구하기 위해서는, here를 짓기 이전에 먼저 지어야 하는 건물들 (g[here]에 속한 건물들) 중 time(건물)이 가장 큰 것 + spend[here], 이것만 구하면 충분하겠죠? 만일 g[here]가 비어있다면, time(here)는 그냥 spend[here]가 될 거고요. 이 답을 구하는 데에 previousWeight 같은 변수는 필요하지 않습니다.

식으로 표현해보자면:

time(here) = 

  1. !g[here].empty(): max(time(g[here][0]), time(g[here][1]), ..., time(g[here][g[here].size() - 1])) + spend[here]
  2. else: spend[here]

가 될 것입니다.

sotter1020   2년 전

감사합니다! 해결은 되었는데 제가 다이나믹 프로그래밍에 대해 오해를 하고 있는게 있는거 같네요!

공부에 큰 도움이 되었습니다! 좋은 하루 되세요!

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