탑다운 vs 바텀업?

• 탑다운의 경우, 공간적으로 100만이기 때문에 탑다운으로 해도 괜찮다고 생각하지만, 문제가 있다.
  -> go(x) = min(go (x-1) , go( x /2 ) , go( x / 3)) 이기 때문에

-> go(x-1) 에 의해서 재귀가 100만번이 발생한다.

스택 영역 개념

• 개념
  

• 좀더
  

• 보충
  : 100만이라고 하더라도 , 탑다운에서 logN이라고 하면 상관없다. 하지만, 지금같이 100만번 발생하는 경우라서 문제다.

결론

• 탑다운의 경우, 공간복잡도만 생각하는 것이 아니라, 재귀가 몇번 호출하냐? 가 중요하다.
  -> 대중 20만 정도 이할라고 한다면 탑다운으로 하자.