[whitefeather]

안녕하세요 조교님 Hw5 Ex4질문드립니다.
모든 경우를 일일이 고려하는 것보다 실행비용의 측면에서 효율적인 프로그램을 작성해야 한다고 하셨는데 name_lst들에 대해 lst들 전부를 확인하는 알고리즘이면 감점인건가요??

1. name_lst크기가 M, lst 크기가 N이면 일단 name_lst에 해당하는 위치 lst에서 찾아서 위치 갖고오는데에 N*M 걸릴 것 같은데.. 전체 코드 실행시간이 저기 붙을 앞의 상수를 줄여야하는 건가요??

2.그나마 생각해본게 lst의 일부만 찾는 방법으로 미리 위도, 경도로 나눠놓고 하는 경우인데 이 경우 2차원 평면이랑 다르게 곡면이라 깔끔하게 안 나눠질 것 같은데... 생각을 잘못하고 있는건가요?ㅠㅠ

감사합니다.

[김진영_]

수행시간과 점수 관련해서는 아래 타래의 마지막 답변을 참고 바랍니다. https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=6082&sid=9dc7bcfbc4fac4266179dd23f2eabef1

상수배 차이라면 시간복잡도가 같은 것으로, 실행비용의 측면에서 효율적인 프로그램으로 보기는 어렵습니다. 다만 본인의 구현에 따라, 또는 데이터의 형태에 따라 일부 큰 데이터에 대해서도 제법 빠른 답을 내는 휴리스틱을 만들 수도 있을 것입니다.

위도와 경도 범위에 대해서는 아래 공지 또한 참고 바랍니다. https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=6091

2차원 평면이랑 다르게 곡면이라 깔끔하게 안 나눠지는 것이 맞습니다만, 앞으로 질문하신 분이 실제 세상의 데이터를 가지고 프로그래밍하는 일이 생긴다면, 깔끔한 입력을 만나는 운좋은 일은 정말 드물다는 것을 겪게 되실 거라는 생각이 듭니다. 말씀하신 방향으로 생각을 발전시켜 보시면 하나의 답을 찾을 수 있지 않을까 생각합니다.