SICP 1.14 질문입니다.

Question

문제: 11센트를 동전으로 바꿀 때, 1.2.2절의 count-change 프로시저가 만들어 내는 프로세스를 나무꼴로 그려 보아라. 바꿀 돈이 늘어남에 따라 프로세스가 거치는 단계 수와 기억공간의 크기는 어떤 자람차수를 보이는가? (즉 어느정도로 자라나는가?)문제를 보신지 오래된 분들에게 기억을 떠올려 드리자면, cc프로시저는 가장 큰 액수의 교환 가능한 금액으로 한번 교환한 경우와, 아예 교환하지 않은 경우로 나눠서 돈을 동전과 지폐로 바꾸는 경우의 수를 반환하는 프로시저입니다. 이 문제를 풀 때, 시간복잡도를 구하는 것은 이해가 되었습니다.그런데 공간 복잡도가 O(n)이라는 것은 납득이 안되어서 설명이 필요합니다.다른분들의 풀이를 보면, &#34;가장 길게 뻗은 가지가 n에 비례하기 때문에 기억공간이 n만큼 필요하고, 따라서 공간복잡도는 O(n)이다.&#34; 라는 설명이 대부분인데, 제 생각에는 가장 긴 가지를 제외한 나머지 가지들도 n에 따라 메모리를 차지하는 비율이 유의미하게 높아지고, 그렇다면 공간복잡도가 O(n)은 아니지 않은가하는 의문이 들었습니다.설명해주실 수 있는 고수분 찾습니다.

엡실론 · Accepted Answer

무슨 문제인지는 잘 모르겠지만, 재귀호출 그래프인것 같네요. 재귀 호출은 DFS입니다. 한순간에는 하나의 가지만 탐색합니다. 제일 긴가지의 (cc 0 1)과 (cc 11 3)의 자식인 (cc 1 3)이 동시에 메모리를 차지할 일이 있을지 생각해보세요.

19학번이유진 · Answer

&#64;엡실론오 확실히 DFS방식이라면 가장 긴 가지를 필요한 메모리의 양으로 보는 것이 맞겠군요. 감사합니다.제가 왜 헷갈렸는지 알겠습니다.무심결에 인자먼저 계산법이 아닌 정의대로 계산법을 사용해서 문제를 풀려고 했습니다.그러다보니 DFS가 아닌 BFS방식으로 생각을 했고 정답들을 봐도 이해가 되지 않았습니다.답변 감사합니다.

SICP 1.14 질문입니다.

2개의 답변

Q&A 목록