| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2006년 3월 12일 일요일 오후 06시 30분 41초 제 목(Title): Re: A를 B로 바꾸어 풀면.... 알고리즘 책이라면 정렬을 convex hull 문제를 이용하면 되겠네요. x_1, x_2, ..., x_n을 정렬할 때, (x_1, x_1^2), (x_2, x_2^2), ... 점의 convex hull을 구하면 정렬을 할 수 있습니다. convex hull 문제의 lower bound가 n log n이라는 걸 증명하는데 쓰입니다. 그밖의 문제의 lower bound 관련 증명 중에서 골라쓰면 됩니다. -- 박.. |