dimss   2년 전

시간초과가 나와서 질문드립니다.

질문 게시판에 검색도 해보고 글을 다 읽어 봤지만 어디가 잘못됬는지 모르겠습니다.

제가 작성한 부분의 소스가 어디서 잘못되어서 시간초과가  뜰까요.

seico75   2년 전

메모하는 부분이 없네요. 

그리고 메모는 0/1 의 수를 메모해야하지 않을까요?

djm03178   2년 전

메모장에 펜을 그은 적이 없으니 아무것도 메모가 항상 안 되어 있는 게 당연합니다.

dimss   2년 전

@seico75
기본 피보나치도 안되서 왜 안되는지 확인하고 하려고요 ㅠ 

numbers[temp] = fibonacci(temp); 저는 이게 메모라고 생각하고 있는데 잘못생각한걸까요?

djm03178   2년 전

펜을 아예 그은 적이 없는 건 아니군요. 하지만 이건 메모이제이션이라기보다는 결과를 그냥 저장해둔 것에 가깝습니다. 메모이제이션이라고 하려면, 그 중간 과정에서 나온 값들도 모두 기록해둬야 합니다.

예를 들어 fibonacci(40)을 구하려면 fibonacci(0)부터 fibonacci(39)까지를 모두 호출하게 되는데, 그 때마다 각각의 결과를 구할 수 있는데 이들을 바로바로 저장해두면 좋지 않을까요?

dimss   2년 전

@djm03178

답변감사드립니다!

seico75   2년 전

기본 피보나치에 중점을 두어서 

조금더 자세히 설명을 드리면...31~35줄은.. 아래와 같이 바뀌어야 할 껏 같네요..

말씀하신 것 처럼 main에서 memo를 하면 전체 프로그램 수행에서 한번만 memo 가 됩니다.

우리의 목적은 중간 저장 결과를 모!두! 저장해야하니까 아래와 같이 재귀 함수 내에서 계산된 것을 모두 저장해야 합니다.


돌려보지 않고 음주 코딩이어서 감안하고 봐주세여.

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