1. Introduction 코딩을 하다 보면 꼭 전체를 정렬할 필요는 없는데 n번째로 큰 원소, 정확히는 n째 인덱스의 값을 얻고 싶을 때가 있다. 예를 들어, 한번 뽑고 나면 다시 섞여버리는 리스트라던가... 필자는 백준에서 문제를 풀다가 어떤 문제에서 존재를 알게되었는데, 처음에는 단순히 성능 "좋은 소팅 알고리즘을 요구하는 문제인가 보다.." 하고 생각했다. 하지만 계속 틀려서 다른 사람들의 답을 찾아보니 $O(n)$ 수준의 시간복잡도를 요구하는 문제였다. 그래서 이번엔 "선택 정렬에서 k까지만 정렬하고 바로 출력하자" 하고 제출하니 또 fail. 생각해보니 이렇게 접근하면 k가 적을 때나 빠르지, 후반으로 갈수록 배열의 대부분을 정렬하니 걍 $O(n^2)$이나 다름 없었다. 그런데 더 찾아보니 ..

1. Uniform binary search 이진탐색의 mid는 현재 값에서 항상 일정한 값 만큼만 차이나게 된다. 즉 현재 a[mid]의 값을 검사했다면 다음에 검사할 값은 a[mid + k] or a[mid - k] 이다. 따라서 매 루틴마다 다음 mid까지의 거리 k를 미리 look-up table에 저장해둔다. 이 결과를 통해 mid를 정하는 산술연산이 불필요하게 된다. 같은 배열에 대해 많은 쿼리를 처리해야하는 환경에서 빠르게 동작한다. 2. Exponential binary search 이 방법은 target의 범위를 고정하는 방법이다. 시작부터 bound의 범위를 2배로 늘려가며 target의 상한을 찾는다. 상한을 찾았으면 target의 범위는 [bound / 2, bound+1] 사이에 ..

1. Introduction 이진탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이다. 해시 같은 매핑 기반의 기법을 제외한다면 가장 빠른 탐색 속도를 보장한다. 2. Method 이진탐색의 핵심은 전체 탐색범위를 반으로 나눠서 찾고자 하는 원소 (이하 target, $T$)가 없을 것으로 기대되는 쪽을 버리는 것이다. 이를 통해 탐색범위는 기존의 탐색범위의 $1\over2$이 되고, 이 새로운 탐색 범위에 반을 버려가는 과정을 반복하여 결과적으로 target을 찾아내는 방법이다. 과정을 자세하게 알아보자. 탐색을 원하는 구간 [a, b]에 대해 a를 low, b를 high라고 하자. (당연히 low, high는 index이다) low와 high의 중간 값을 mid라고 하자. 탐색할 리스트를..