게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

숙제 4-2 추가 힌트

 
글 쓰기   답변 달기     게시판 인덱스 -> 4190.310 Programming Languages (Spring 2021)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
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
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 4190.310 Programming Languages (Spring 2021) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay