| [ QuizWit ] in KIDS 글 쓴 이(By): scalar (스칼라(數)) 날 짜 (Date): 1999년 11월 6일 토요일 오후 08시 03분 02초 제 목(Title): Re: [Q] duplicate 구별하기? 집합 S가 [0,m] 범위의 n개 정수들로 이루어진 집합일 때, 중복된 원소들(duplicates)을 찾고, 이 때, 사용 가능한 메모리는 O(n)이고 시간은 O(n)인 알고리즘을 만들라는 것 아닌가요? 만약, m이 n과 관련이 없는 상수(constant)라면 O(n)시간에 쉽게 찾을 수 있습니다. 그건 O(m)의 메모리를 사용하여 각각의 정수가 나타나는 빈도를 세어보면 됩니다. 또한 m이 O(n)인 경우도 위 방법으로 쉽게 할 수 있습니다. 사용 가능 메모리가 O(n)이니까. 문제 조건에서 m<<n이 만약 m이 n보다 무지 작다라는 표시라면 위 방법으로 쉽게 할 수 있겠지요. 만약 m이 n을 넘는 asymptotic notation으로 표시된다면, O(n) 시간에 처리하는 알고리즘을 만들 수 없습니다. 이 경우 sorting 을 한 뒤에 다시 한번 sorting된 것을 scan해야 하지요. 따라서 이경우는 O(n log n) 시간이 소요됩니다. >>>>>>>>>>>> rk.ca.gnagos.2balgla@ralacs >>>>>>>>>>>>>>>>>>>>>>> 내가 사랑하는 모든 이에게 항상 기쁨과 축복이 있기를 그리고, 나를 사랑하는 모든 이에게도 ......... <<<<<<<<<<<<<<<<<<<<<<<<<<<< scalar@alglab2.sogang.ac.kr <<<<<<< |