[최재민]

제가 구현한 방식대로는 step이 1000 이상 넘어가면 시간이 몇초 이상 걸리게 되는걸 발견해서 질문을 드립니다.
조교님께서 모범답안은 1초 이내에 실행이 끝난다고 하셨는데 도대체 어떻게 구현을 해야 그렇게 되는지 잘 모르겠네요...

저는 이 문제를 (상점 이름 X 확률)의 리스트를 계속 키워나가는 식으로 구현을 했는데요,
예를 들어 상점 D에 대해, step=2라고 하면
step=1: '((B . 0.7) (C . 0.4) (D . 1))
step=2: '((A . 0.7) (B . 0.12) (B . 0.7) (C . 0.4) (D . 1))
이런 식으로요. (트리 구조의 leaf만 기억을 하는 구조입니다)
그리고 마지막에 나오는 리스트의 확률들을 다 더한 다음에 (1/상점의 개수)를 곱해주면 D에 대한 최종 확률이 나오게 했습니다.

어떻게 구현을 하던 트리 구조와 비슷한 구조를 구현해야 하는 것 같은데...
힌트라도 조금 주시면 감사하겠습니다!

[강지훈]

하나 힌트를 드리자면,
(B . 0.12)와 (B . 0.7)를 (B . 0.82)로 합치는 방식으로 최적화를 꾀해볼 수는 있겠습니다.
_________________
강지훈
프로그래밍의 원리 조교

Jeehoon Kang
TA, Principles of Programming