devouring123   2년 전

주석 처리 되어 있는 부분이 재귀함수로 구현한 부분이고요

처음에 재귀로 구현하였을때는 시간 초과가 나서 메모이제이션을 사용해서 DP로 구현(?) 하였습니다.

그러나 어디서 잘못되었는지 메모이제이션을 한 후에 결과가 제대로 나오지 않는것 같습니다

코딩고수님들의 좋은 답변 기다리겠습니다. 감사합니다.

게시판의 모든 반례를 넣어보았으나 잘 작동합니다.

djm03178   2년 전

메모이제이션을 했을 때의 문제점을 물으시는 거라면, 메모이제이션 한 코드 쪽을 활성화해서 주셔야 합니다. 좀 더 정확하게 말하면, 제출해서 틀렸던 코드를 그대로 올려주셔야 합니다. 그리고 여러 줄 주석은 /* */로 쓰시면 한 번에 처리할 수 있는데, 매 줄마다 //로 되어 있어서 지우기도 번거롭습니다.

devouring123   2년 전

메모이제이션을 했는 코드를 활성화 시켰을때 결과가 제대로 나오지 않기 때문에 글을 올렸습니다.

답변자께서 약간 오해를 하신 것 같은데 메모이제이션을 하지않은 재귀 코드를 작동시켰을 때는 작동이 잘 되었으나 그 재귀함수를 메모이제이션코드로 바꾸어 했을 때는 작동이 잘 되지 않았기 때문에 이 두개의 코드를 보시고 어디에서 차이가 나는지 알고 싶기 때문에 그래서 두개의 코드를 한번에 올려 한쪽을 주석처리 해 놓은것입니다. 

그리고 여러줄 주석의 경우에는 vs에서 한번에 주석으로 변환시킬 경우 저렇게 표시가 되어서 싹 끍어서 한번에 주석 해제 기능이 있기 때문에 그렇게 올렸습니다. 다른 프로그램에도 주석 해제기능이 따로 있는 것으로 알고 있습니다. 그것을 사용하시면 편하게 주석처리를 지우실 수 있을 것 입니다.

djm03178   2년 전

그런 기능이 있는 것은 몰랐습니다.

그러나 제가 이해하기로는 질문의 요점은 "왜 메모이제이션을 한 코드가 틀렸는가"이지, "왜 메모이제이션을 안 한 코드는 맞는가"가 아닙니다. 그러면 메모이제이션을 한 코드에서 문제점을 찾아야 하는 것이지 메모이제이션을 안 한 코드는 별로 볼 필요가 없습니다. 보니까 두 코드의 차이가 한 두 줄도 아니고, score_stair 함수의 구현 방법 자체가 매우 다른 것 같은데 둘의 차이를 비교하자고 하셔도 별로 드릴 말씀이 없습니다. 그리고 무엇보다 말씀드렸듯이, 틀렸던 코드를 그대로 올려주셔야 제출했던 것과 동일한 환경에서 테스트를 해볼 수 있는 겁니다. 주석 처리한 것 외에는 다른 게 없다고 하셔도, 정말로 한 글자도 추가적으로 다른 게 없는지는 답변자 입장에선 알 수가 없습니다.

devouring123   2년 전

틀린코드 그대로 소스코드를 변경하였습니다. 혹시 찾으신다면 댓글달아주시면 감사하겠습니다.

djm03178   2년 전

다음과 같은 반례가 있습니다.

devouring123   2년 전

결과가 제대로 나오지 않는다는 것을 알고 있습니다. 제가 묻고 싶은것은 "이 코드가 맞았는지 또는 틀렸다면 이런 반례가 있기 때문에 틀렸는지" 가 아니라, 위의 코드를 재귀함수로 구성했을 때의 경우 맞는 예제들이 어째서 DP로 구현했을때 틀렸는지를 묻고싶었습니다. 질문을 잘못 이해하신것 같습니다.

djm03178   2년 전

"게시판의 모든 반례를 넣어보았으나 잘 작동합니다." 라는 것이 메모이제이션을 했을 때를 말씀하신 걸로 생각했는데, 아니었나 보군요. 질문의 요점을 처음부터 확실하게 해주셨다면 좋았을 텐데, 두 코드에 대한 이야기를 섞어쓰셔서 오해를 한 것 같습니다.

저 예시를 넣어보면 score_stair(3, true) 가 호출되는 시점에 score[1]과 score[2]가 이미 각각 2와 7로 결정이 되어 있는 상태입니다. 그런데 score[2]의 7은 이미 1, 2를 연속으로 밟은 상태임에도 불구하고, score[3]은 22번째 줄에 의해 세 계단을 모두 밟은 값으로 계산하게 됩니다.

메모이제이션을 할 때는 모든 상태에 대한 처리를 개별적으로 해줘야 됩니다. score에 담기는 값은 다음 계단을 밟는 것과 밟지 않는 것에 따라서 별개로 저장이 되어야 한다는 뜻입니다.

devouring123   2년 전

아 그렇군요 그럼 dp 배열을 두개로 나누어서 해야겠습니다. 많은 도움이 되었습니다. 감사합니다.

devouring123   2년 전

DP 배열을 두개로 나누어서 풀어보니 풀렸습니다. 많은 도움 감사합니다.

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