게시판 인덱스

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

HW5 채점결과 안내 + ex4 코멘트

 
글 쓰기   답변 달기     게시판 인덱스 -> L444.200 Computational Thinking and Practice (Fall 2017)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
김진영_



가입: 2009년 12월 9일
올린 글: 337

올리기올려짐: 2017년12월22일 16:34    주제: HW5 채점결과 안내 + ex4 코멘트 인용과 함께 답변

다섯 번째 숙제의 채점이 완료되었습니다. 마지막까지 고생 많으셨습니다.
http://ropas.snu.ac.kr/~ta/444.200/17/hw5.txt

다시 한번 숙제 관련 유의사항을 확인해 주시기 바랍니다.
(http://ropas.snu.ac.kr/~ta/444.200/17/hw-readme.pdf)

o 채점결과표 보는 법
- 학번은 일부 자리를 가렸습니다. 이름이 없으신 분은 아무 문제도 제출하지 않으신 분들입니다.
- a는 자동채점, m은 수동채점 결과입니다.
- 각 10점 만점이며 따라서 총합은 80입니다.
- 지각 페널티가 적용된 결과입니다.

o 자동채점에 사용된 데이터
- 홈페이지에서 받아보실 수 있습니다. 이의제기 기간 이후 접근을 제한합니다.
.json 파일들이며, 기존과 양식이 동일합니다.
("n_data" 아래에 데이터의 갯수가 있습니다. "datalist" 아래에 데이터들의 리스트가 있습니다. 리스트의 각 원소는 [입력데이터, 정답] 입니다. 인자가 여러 개인 경우 입력 데이터는 인자들의 리스트로 주어집니다.)

o 이의제기
- 이의제기 공지를 참고하시어 메일 주시기 바랍니다. (https://ropas.snu.ac.kr/phpbb/viewtopic.php?p=14878)
- 시간이 많이 남지 않아, 아래에 빈번했던 실수들에 대해 언급해 드립니다. 위의 공지와 함께 참고해보시면 의아하신 부분이 많이 풀릴 거라 생각합니다. 여전히 이의가 있으신 경우, 12월 25일 (월)까지 메일 주시기 바랍니다.
- 실습시간에도 설명드렸습니다만, 숙제4의 상세한 의도와 여러분들의 답안을 보고 느낀 점들에 대한 코멘트를 작성해보았으니 함께 확인해보시기 바랍니다.


o 빈번했던 실수

[모든 문제 공통]
- 숙제 5인데도 여전히 문법이 어긋나거나, 특수한 경우가 아닌데도 오류를 내고 프로그램이 비정상 종료하는 경우들이 있었습니다. 이 경우 지금까지 숙제에서 그래왔듯이 자동채점 점수를 전혀 받으실 수 없습니다. 사소한 실수야 있을 수 있지만 마지막 숙제에서 나올 수준의 숙제라고는 보기 힘든 것들이 대부분이었습니다. (== 대신 =를 썼다거나, True/False대신 true/false로 쓴 경우 등.) 아주 작은 입력 데이터를 넣어 한 번만 실행해 보았어도 잡을 수 있는 실수들이라고 봅니다. 마지막 숙제인만큼 문법에러와 비정상 종료에 대해서는 엄격하게 채점하였습니다.
- 표준 라이브러리 외의 import를 포함하는 경우 채점 환경에서 프로그램이 실행되지 않아 자동채점 점수를 받으실 수 없습니다. import는 표준 라이브러리에만 사용해 달라는 점을 여러 번 말씀드렸고, 숙제 4때에 특히 exercise마다 독립적으로 실행되는 프로그램을 제출하라고 반복적으로 말씀드렸습니다. 실습시간에 채점이 어떻게 이루어지는지에 대해서도 여러번 말씀드린 것으로 기억합니다. 여러 명의, 여러 문제의 코드를 채점하는 입장에서 본인이 제출하신 파일 이름명 그대로 다른 exercise들과 같은 디렉토리에서 채점이 이루어진다고 가정하신 것도 저로서는 조금 의아합니다.
- 여러분이 작성한 함수가 리턴해야 하는 값이, 구하도록 요구된 답과 타입이나 형식이 맞지 않는 경우도 종종 있었습니다. 이런 경우 자동채점 점수를 받으실 수 없습니다. 예를 들어: ex2와 ex3은 이름들의 리스트를 만들어야 합니다. 이름이 아닌 다른 값이 들어있거나, 리스트가 아닌 다른 자료구조를 돌려주시면 안되겟지요. ex1은 리스트의 길이가 2여야 합니다. ex4의 리스트의 길이는 인자로 주어진 name_lst의 길이와 같고 그 순서가 대응되어야 합니다.

[ex1]
- (당연한 소리지만) 조건에 맞게 정렬을 잘 해야 합니다.
- 조건에 맞는 일상적인 곳이나 특별한 곳이 없는 경우 빈 리스트를 만들어야 합니다.

[ex2, ex3 공통]
- (당연한 소리지만) 조건 처리를 잘 해야 합니다. 게시판에서 논의된 질문/답변도 많으니 참고해 보시기 바랍니다.
- 중복되거나 불필요한 연산이 있는 경우 큰 데이터에 대해 시간이 비정상적으로 오래 걸리게 됩니다. 이런 경우 해당 데이터에 해당하는 자동채점 점수를 받으실 수 없으며, 수동채점에서도 정도에 따라 감점이 있습니다.

[ex4]
- 위치정보들의 리스트의 길이를 n, 가장 가까운 다른 위치를 알고 싶은 이름들의 리스트를 m이라고 합시다. 모든 길이를 다 계산해 가장 짧은 거리를 찾는, 가장 단순한 알고리즘의 시간복잡도은 O(nm)입니다. 실행비용의 측면에서 효율적인 프로그램을 작성하도록 명시되어 있고, 게시판 질문도 이와 같은 취지로 답변을 드렸습니다. 이보다 시간복잡도 측면에서 효율적인 프로그램으로 볼 수 없거나 심지어 더 비효율적인 경우, 점수를 많이 드릴 수 없었습니다.
- 조금이라도 이보다 빠른 프로그램을 만들기 위한 시도를 한 경우 자동채점 점수와 관계없이 점수를 최대한 드렸습니다. 아래에서 좀더 자세히 설명드리겠습니다.



o ex4 의도와 가능한 풀이들

이론적으로 가장 "옳은" 답안이라면 k-d tree 또는 voronoi diagram (또는 delaunay triangulation)이라는 것을 응용하는 것이겠으나, 당연히도 이것이 의도한 풀이는 아닙니다. 마지막 실습시간에 말씀드린 내용인데, 출석하지 않으신 일부 학생분들이 이 부분에 대해 조금 오해하고 계신 것 같아 지금 이 항목을 작성하고 있는 것이기도 합니다. (물론 관심이 있으신 분들이라면 구글링해 보시면 이와 관련된 자료와 코드들을 찾을 수 있기는 하겠습니다만, 의도한 바는 아니었습니다.)

실습시간에도 말씀드렸고 문제에도 일부 적혀 있습니다만, ex4의 의의는 단순한 문제더라도 빠른 시간에 항상 옳은 답을 내기가 어려운 경우를 실제로 겪어보고, 이를 지금까지 배우고 실습한 방법들을 응용하여 돌파해 보라는 것입니다.

지금까지 실습한 수준에서 크게 아래 세 가지 정도의 풀이가 가능할 것으로 생각하였고, 이 중 일부를 시도한 경우 상대적으로 빠른 시간에 정답을 낼 수 있는 데이터를 만들어 자동채점에 활용하였습니다. 또한, 이와 유사한 수준의 시도를 한 경우 자동채점 결과와 상관없이 수동채점에서 매우 높은 점수를 드렸습니다.

- 병합정렬이나 이분탐색처럼, 문제를 반으로 쪼개 나가는 재귀적인 방식의 풀이가 가능합니다. 주어진 점들의 집합 S를 기준에 따라 정렬하여 (가장 단순하게는 위도순) 반에 가까운 두 집합 S1, S2로로 나누고, 각각의 점의 집합에 대해 같은 부분문제를 푼 뒤, 이를 합치는 방법입니다. 합칠 때에는, S1의 점 p1과 가장 가까운 점이 S2의 점이 될 수 있는 경우를 추가적으로 고려해주어야 하겠지요. (반대의 경우도 마찬가지) 그렇다고 모든 점에 대해서 고려한다면 시간복잡도가 단순한 방법과 성능이 다를 바가 없으니, 효율적인 계산이 필요합니다. 예를 들어 S1의 점 p1과 지금까지 가장 가까운 S1 위의 점 p2를 알고 있다면, p1과의 거리가 dist(p1, p2)보다는 작은 S2위의 점에 대해서만 추가적으로 고려한다거나 하는 등.

- 숙제3 문제3과 비슷한 방법으로도 해결이 가능합니다. 소수점 이하 여섯째짜리까지만 고려하고 있으므로, 위도와 경도 기준으로 영역을 반씩 몇 번 나누다 보면 한 영역 안에 한 점만 들어가는 순간이 금방 찾아옵니다. 자식이 네 개인 트리로 만들어 둔 뒤 탐색해볼수도 있을 것이고, 인접한 영역들을 기억해 두고 있다가 근처에서만 찾아보는 방법도 가능할겁니다.

- 문제의 제약조건들로 추가적인 휴리스틱들이나, 불필요한 계산을 줄이는 가지치기들을 생각해 보실 수 있을겁니다. 몇가지만 적어 보겠습니다.
(1) 거리가 d 이하인 점에 대해서만 고려하면 됩니다.
(2) 소수점 이하 여섯째자리까지만을 고려하고 있습니다. 서로 다른 점은 위도와 경도의 차이가 최소한 0.000001은 난다는 이야기입니다. 다닥다닥 붙어 있는 점이 없기 때문에 고려할 상황이 조금은 적어집니다.
(3) 큰 도움은 아닐지도 모르겠습니다만, 위도와 경도의 범위를 대한민국 주변의 값으로 게시판에 추가적으로 제한해 드리기도 했습니다.

- 무작위를 동원하는 풀이도 가능하고, 실제로도 제법 잘 동작합니다. 먼저, 지금까지 나열한 풀이를 이용하면서 함께 무작위를 적절히 섞어서 사용해볼 수도 있습니다. 위도 순으로 정렬할 때 위도가 같은 경우 경도에 대해서는 랜덤하게 섞는다든지, 인접한 점을 찾을 때 모든 경우를 다 고려하지 말고 랜덤워크를 몇 번 해본다던지 하는 방법등이 가능할겁니다. 또한, 조금은 수학적인 지식이 동원된다고 볼 수도 있겠으나 무작위 단독으로도 만들어볼 수도 있습니다. 예를 들어, 모든 점들을 랜덤하게 1차원으로 투영한 뒤 그 위에서 근처의 점들에서 d 이하가 될 수 있는 거리를 한정한 뒤 고려하는 방법이 있습니다. 운이 나쁘다면 오래 걸릴 수도 있겠으나 항상 옳은 답을 보장하는 무작위 알고리즘입니다. 그게 아니라면 랜덤한 투영을 반복적으로 시도하는 몬테카를로식 방법도 가능합니다.


직접 코드를 하나하나 살펴보니 많은 학생들이 이런저런 시도를 해보셨습니다. 아마 조금 더 시간을 들여 생각해보셨다면 더 다양하고 흥미로운 방법들을 시도해보셨겠구나 하는 코드들도 있었습니다. 고생스러우셨겠지만 좋은 경험으로 남았기를 바랍니다.
위로
사용자 정보 보기 비밀 메시지 보내기 이메일 보내기
김진영_



가입: 2009년 12월 9일
올린 글: 337

올리기올려짐: 2017년12월23일 2:06    주제: 인용과 함께 답변

죄송합니다만, 3번 문제의 데이터에 오류가 있습니다. (지적해주신 장태준님 고맙습니다.)

오류를 수정한 입력 데이터로 다시 채점한 뒤 결과를 곧 올려드리겠습니다.

왜 오류가 발생했고 확인하지 못했었는지, 어떻게 수정했는지에 대해서도 간략히 설명 드리도록 하겠습니다. (postmortem이라고 합니다. https://en.wikipedia.org/wiki/Postmortem_documentation)

혼선을 드려 죄송합니다.
위로
사용자 정보 보기 비밀 메시지 보내기 이메일 보내기
김진영_



가입: 2009년 12월 9일
올린 글: 337

올리기올려짐: 2017년12월23일 4:02    주제: 인용과 함께 답변

3번 문제를 오류를 수정한 새로운 입력 데이터로 재채점하였습니다. 데이터의 크기 (두 리스트의 길이)는 기존과 같습니다. 새로운 데이터가 포함된 파일로 업데이트해 두었으니 확인해보시기 바랍니다.

결론만 말씀드리자면 자동채점 점수가 오르신 분은 없고, 수동채점 점수는 한 분 올려드렸습니다.

새로운 데이터로 채점했을 때의 점수가 기존에 공지한 점수에 비해 낮은 분들이 열 명 가량 있었습니다. (차이는 모두 2점이었습니다. 데이터가 5벌이었으니 기존 데이터에서 k개 정답이었다면 새로운 데이터에서 k-1개 정답이었다는 것입니다.) 이는 기존의 데이터 오류와는 상관없는 데이터의 랜덤성 때문이기도 하고, 이미 공지가 된 상황에서 추가적인 감점을 하는 것은 그것대로 문제가 있을 수 있다고 판단해 기존 점수를 유지하고자 합니다.

다시한번 번거로움을 드려 죄송합니다. 자세한 내용(사후보고서?)은 주말중으로 적어보도록 하겠습니다.

이 이슈 또는 새로 올려드린 데이터와 관련해서도 이의가 있으신 경우, 기존과 마찬가지로 12월 25일 (월)까지 메일 주시기 바랍니다.
위로
사용자 정보 보기 비밀 메시지 보내기 이메일 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> L444.200 Computational Thinking and Practice (Fall 2017) 시간대: GMT + 9 시간(한국)
페이지 11

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


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