반응형 devide and conquer1 이진 탐색(Binary Search) 이진 탐색(Binary Search) 어떤 decision problem의 답이 단조성(monotonicity)를 띌 때, 정답을 포함하는 구간의 크기를 절반씩 줄여가며 query 횟수를 최대 O(logN)회로 제한할 수 있다. mid보다 찾으려는 수가 작다면 mid의 오른쪽 원소들을 볼 필요가 없을 것이고, mid보다 찾으려는 수가 크다면 mid의 왼쪽 원소들도 볼 필요가 없을 것이다. divide-and-conquer 방식으로 접근해보자. Devide arr[1..N]가 arr[1..mid]와 arr[mid..N]으로 divide. Conquer A[mid] = x : return mid A[mid] < x : select A[mid + 1..N] for the next iteration. A[mid.. 2024. 3. 26. 이전 1 다음 반응형
