postbg   1년 전

계속 메모리 초과가 나는데, 더이상 어디를 고쳐야 할지를 모르겠습니다.

부족한 실력에 한마디 조언부탁드립니다

yukariko   1년 전


계산과정을 잘 생각해보면

cache가 꼭 모든경우에 대해 알고있어야할 필요는 없습니다.

피보나치를 예로 들어볼게요..

fibo(100) 을 구하려면 fibo(99) 와 fibo(98) 을 알아야되고 쭉 내려가다보면 1~100개가 필요합니다.

하지만 fibo(1) , fibo(2) 를 가지고 시작하면 fibo(1) 대신 1과2를가지고 만든 fibo(3)으로 대체하고, fibo(2) 를 fibo(4) 로 대체한다면

2개의 캐시만을 가지고 fibo(100)을 구할 수 있습니다. 내려가기문제도 똑같은 구조를 갖기 때문에 같은 방법으로 문제를 해결이 가능합니다.

koosaga   1년 전

여담이지만 배열 메모리가 300000 * 2 * 4byte = 2.4MB로 아마 아슬아슬하게 4MB 안에서 해결이 가능하지 않을까 합니다.4MB를 넘기는 이유가 재귀 함수를 사용해서 (스택 메모리라고 자세한 건 검색해보세요 ^^;)가 아닐까라고 추측하는데 재귀 함수 대신 반복문으로 해결해도 괜찮을 거 같습니다.

postbg   1년 전

주중에 너무 바빠서 이제서야 답글을 읽었네요

yukariko님 먼저 답변 감사드립니다. 정말 조언해주신대로 다시 생각해보니 cache크기를 확 줄일 수 있더군요.

koosaga님 역시 답변 감사드립니다. 저도 스택메모리 때문일 것이라고 생각했는데, iteration으로 바꿀 생각은 하지 못했었네요. 많이 배웠습니다.

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