chocurlwoo   4년 전

memo에 각 숫자의 최소값을 저장시키면서 풀어보려고 하는데요..

이상하게 n이 7까지는 잘 뽑아주는데 n이 8이상이면 unsupported operand type(s) for +: 'NoneType' and 'int' 에러가 뜹니다.

왜 n이 7까지는 잘 돌다가 8부터는 에러를 표시하는 걸까요.

아래에 있는 피보나치 수열 구하는 방법이랑 기본적인 방법은 같다고 생각하는데 잘 모르겠습니다 ㅠㅠ

sait2000   4년 전

i가 memo에 있을 때 리턴 하는 부분이 안 보여요

chocurlwoo   4년 전

sait2000님 감사합니다 ! 

코드를 수정해보았는데 잘 작동되다가 n이 2000쯤 되면은 Error가 뜨더라구요..

왜 그럴까요...  흑 기초가 없다보니 너무 어렵네요 ㅠㅠ

chocurlwoo   4년 전

검색해보니 재귀제한? 이 Limit가 걸려있더라구요.. 

여기서 질문이

  1. 재귀깊이를 엄청나게 늘리면 (예를들어  sys.setrecursionlimit(100000000...) 이런식으로 늘려도 runtime error 가 뜨더라구요. 혹시 파이썬 자체적으로 재귀 깊이의 상한선이 있는건가요?)

2. 본질적으로 제가 짠 코드의 알고리즘이 무엇이 잘못됬는지 궁금합니다. 다른 코드랑 비교했을때 코드가 실행되는 n내에선 값이 같게 나오는걸 봐서는 알고리즘은 맞다고 생각되는데, 재귀깊이를 줄이는 알고리즘이 있을까요??

혼자서 공부하다보니 생각하면 생각할수록 궁금한점이 많아지네요.. 

sait2000   4년 전

  1. 정확히는 모르겠고 저는 매번 9**9로 설정합니다.
  2. 다른 코드는 어떤 언어 말씀하시는 건가요. 일단 일반적인 방법으로는 동적계획법을 반복문을 이용해서 하는 방법이 있습니다. 이른바 bottom-up DP라고 하죠. 지금처럼 재귀 호출하면서 메모이제이션 하는 건 top-down DP라 하고요. 그리고 이 문제에만 적용되는 방법은. 잘 생각해보면 2의 배수가 될 때까지 1을 뺀 다음 2로 나누거나 3의 배수가 될 때까지 1을 뺀 다음 3으로 나누는 경우만 생각하면 됩니다. 증명은 귀찮으니까 생략합니다. 이렇게 하면 재귀호출 회수가 최대 대략 log2 n쯤 되니까 재귀 깊이가 줄 겁니다 아마.

근데 1일 때 0 아닌가요

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