shkim
가입: 2019년 7월 30일 올린 글: 86
|
올려짐: 2021년4월6일 1:32 주제: 숙제 4-2 추가 힌트 |
|
|
선 요약:
1. 숙제 문서의 힌트대로 구현하면 큰 입력값에 대해 매우 긴 시간이 걸리는 것이 당연합니다.
2. 문제의 의도는 K- 언어로 나름 복잡한 프로그램도 충분히 구현할 수 있다는 것을 확인해 보는 것입니다.
3. 따라서 알고리즘의 최적화는 평가 항목이 아니며 4-2 채점시 입력값은 5000 이하의 숫자만 들어올 것입니다.
여러 학생분들이 4-2의 입력값이 큰 경우에 대해 걱정하시는것 같아 추가설명을 드립니다.
숙제 4-2와 4-3의 의도는 수업시간에 정의하고 여러분이 직접 구현한 K- 실행기를 이용해 제법 그럴싸한 프로그램도 문제없이 구현해 실행할 수 있을만큼 표현력이 충분하다는 것을 확인해 보는 것입니다. 특히 4-2의 경우 숙제문서에 직접적으로 힌트를 제공한 것은 알고리즘을 고민하게 하는것이 문제의 의도가 아니기 때문입니다.
메일로 문의주신 학생분의 지적대로 이 알고리즘의 base case는 numch1(n) 뿐이기 때문에, 주어진 액수의 거스름돈 경우의 수가 N개라면 numch1() 함수 또한 총 N번이 호출될 것입니다. Naive한 피보나치 재귀함수가 같은 계산을 이곳 저곳에서 반복하면서 실질적인 값은 leaf에서 1씩만 더하는 것과 비슷하게 생각해 볼 수 있겠네요(https://holycoders.com/algorithms-fibonacci-sequence/ 앞부분). 아마 이 문제도 피보나치와 같이 입력값에 대해 실행 시간이 지수적으로 증가하겠지요.
따라서 입력값이 클 경우 긴 시간이 걸리는게 당연합니다(모범답안의 경우 입력 50,000에 대해 2,083,485,412 라는 답을 내놓는데 약 16초가 걸렸습니다). 숙제 문서에 제공된 알고리즘으로만 구현해도 테스트케이스를 모두 문제없이 통과할수 있고 모범답안 또한 같은 알고리즘으로 구현되었습니다. 실행시간은 평가 항목이 아니고 채점시에는 입력값으로 5000 이하의 숫자만 사용할 것이니 큰 입력값에 대한 걱정은 하지 않으셔도 됩니다.
감사합니다.
TA 김세훈
e-mail: shkim@ropas.snu.ac.kr |
|