| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2007년 12월 5일 수요일 오후 03시 20분 38초 제 목(Title): Re: [Q] 이상한 범위 찾기 > 1 <= m <= n <= N 인 m, n이 있어서, m <= x <= n 에서 a[x]=1, 그 외에 > a[x]=0 입니다. 방법 1: 우선 전체의 1/2을 검사. 그 다음엔 1/4, 3/4을 검사. 그 다음엔 1/8, 3/8, 5/8, 7/8을 검사. 그 다음엔 1/16, 3/16, ... 16/16을 검사.. 이렇게 해서 a[k]=1인 k 값 하나를 찾는다. -> 예상 시간: N/(n-m) 이렇게 하면 1 <= m <= k에서 m을 binary search, k <= n <= N 에서 n을 binary search. -> 예상 시간 2 log N 방법 2: 1/2, 1/4, 3/4, ... 식으로 절반씩 줄여나가는 대신, 1:phi의 비율로 구간을 나누는 것이 조금 더 유리! (1:phi는 황금비) -- 박.. |