"절반씩 나누기"
순차 탐색 (Sequential Search)
순차 탐색이란 이름에서 나타나듯 앞에서부터 차례대로 데이터를 확인하는 방법입니다. 어떤 배열 안에서 내가 원하는 값을 찾고자 할 때, 반복문을 이용해서 처음부터 끝까지 탐색하면서 값을 비교한다면 바로 순차 탐색이 되는 것이죠.
순차 탐색의 장점은 배열 안의 데이터가 정렬되어 있지 않더라도 원하는 결과를 얻을 수 있다는 점입니다. 구현하는 것도 매우 간단하고 쉽구요. 하지만 배열 안의 모든 요소를 확인하기 때문에 시간이 오래 걸린다는 단점이 있죠. 최악의 경우 순차탐색의 시간 복잡도는 O(N) 이라고 합니다.
이진 탐색 (Binary Search)
순차 탐색의 단점을 보완할 수 있는 것이 바로 이진 탐색입니다. 이진 탐색은 데이터를 반으로 나누어 쪼개고, 찾고자 하는 값이 위치한 부분만을 다시 탐색하는 것을 말하는데요. 숫자 맞추기 게임을 생각해보면 조금 더 쉽게 이해할 수 있습니다.
1~100까지의 숫자 중에서 상대방에게 원하는 숫자 하나를 마음 속으로 생각해보라고 한 이후에, up & down 으로 차근차근 범위를 줄여가면서 숫자를 맞추는 게임을 해보신 적 있으신가요? 운 좋게 숫자를 한 번에 맞출 수 있는 가능성도 있겠지만, 문제를 푸는 가장 합리적인 방법은 중간 값을 찾아 범위를 반씩 줄여나가는 것입니다.
이진 탐색은 바로 이렇게 중간 값으로 데이터를 자르고, 찾고자 하는 값이 위치한 부분만 떼어내어 다시 탐색을 진행하는 방법입니다. 전체 데이터를 순회하지 않고 불필요한 부분을 반씩 제거해나가기 때문에, 순차 탐색과 비교해서 시간 복잡도가 O(log2N)이 됩니다. 매우 빠르게 원하는 값을 찾아낼 수 있죠.
대신 이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 만약 데이터가 무작위로 있다면, 아무리 절반으로 나눈다 해도 찾으려는 값이 어디에 위치해있는지 알 수 있는 방법이 없기 때문이죠. 따라서 이진 탐색을 사용하려면 먼저 데이터가 정렬되어 있는지 여부를 반드시 확인한 후에 사용해야 원하는 결과를 얻을 수 있습니다.
이진 탐색의 응용
매일 오전 9시부터 1시간 동안 Toy Problem 이라고 해서 알고리즘 문제를 푸는 시간이 있는데요. 오늘 문제는 부분적으로 오름차순 정렬된 배열에서 찾고자 하는 값을 하고 그 위치를 리턴하는 문제였습니다.
여기에서 부분적으로 정렬된 배열 이라는 것은 왼쪽으로, 또는 오른쪽으로 데이터를 한 칸씩 이동시키고 가장 끝의 데이터는 반대편으로 옮겨 배치하는 식으로 배열을 조정하다 보면, 어느 순간 완전히 정렬되는 배열을 의미합니다. 예를 들어 [1, 2, 0] 과 같은 배열이 있다고 할 때, 데이터를 한 칸씩 오른쪽으로 이동하게 되면 0이 제일 앞으로 오면서 [0, 1, 2] 의 형태가 되어 배열이 정렬되기 때문에 앞에서 말한 조건에 들어맞는 것이죠. 작은 값에서부터 큰 값 기준으로 나열되었으니 오름차순 정렬이 되는 것이구요.
부분적으로나마 정렬이 되었기 때문에 이진 탐색을 이용할 수 있긴 합니다. 대신 그대로 쓸 수는 없고 약간 변형해야 사용이 가능한데요. 기존의 이진 탐색이 단순히 찾아야 하는 숫자와 타겟을 비교해서 범위를 좁혀나갈 수 있었다면, 이 경우에는 조금 더 여러 개의 조건으로 나누어 탐색해야 범위를 좁힐 수 있습니다.
첫 번째 조건
이진 탐색이니 먼저 중간 값을 정합니다. 중간 값이 찾고자 하는 값이라면 더 탐색할 필요 없이 위치를 바로 리턴해주면 됩니다. 이 경우는 바로 종료하면 되겠죠. 하지만 그렇지 않은 경우, 주어진 배열은 부분적으로만 정렬이 된 배열이기 때문에 중간 값 하나만으로는 어디를 탐색해야 할지 알 수 없습니다.
만약 배열의 0 번째 값과 우리가 정한 중간 값을 비교한다면 어떨까요? 최소한 이렇게 하면 중간 값을 기준으로 어느 한 쪽은 정렬된 배열이라는 것 확인할 수 있는데요. 중간 값이 0 번째 값보다 크다면, 최소한 0 번째에서 시작해서 중간 까지의 배열은 오름차순으로 정렬이 되었다는 것을 알 수 있는 것이죠. 반대로 중간 값이 0 번째 값보다 작다면 중간부터 마지막 까지의 값이 오름차순으로 정렬이 되어있을 겁니다.
글로만 설명해서는 이해가 어려우니 예시를 살펴보겠습니다.
let a = [5, 6, 0, 1, 2, 3, 4]
let b = [2, 3, 4, 5, 6, 0, 1]a 는 1 을 기준으로 왼쪽에 3개, 오른쪽에 3개의 요소를 가지고 있습니다. b 는 5 를 기준으로 마찬가지로 왼쪽에 3개, 오른쪽에 3개의 요소를 가지고 있죠.
a 에서 1 이라는 중간 값을 기준으로 0 번째 요소인 5 와 비교해보면 1은 5보다 작기 때문에, 중간 값을 기준으로 오른쪽 부분이 오름차순 정렬이라는 것을 확인할 수 있습니다.
반대로 b 에서는 5 가 중간 값이고, 0 번째 요소가 2 이므로 중간 값이 0 번째 요소보다 작기 때문에 왼쪽 부분이 오름차순 정렬이 됩니다.
이렇게 해서 최소한 어느 한 쪽은 오름차순으로 정렬된 배열이 되는 것을 확인할 수 있게 되었습니다.
두 번째 조건
첫 번째 조건 만으로는 우리가 찾고자 하는 값이 어디에 있는지를 알 수 없기 때문에 두 번째 조건을 추가해줘야 합니다. 두 번째 조건은 첫 번째 조건을 기준으로 해서 결정해야 하는데요.
먼저 중간 값을 기준으로 왼쪽이 정렬된 배열일 경우, 다시 말해서 1. 배열의 0 번째 요소가 중간 값보다 작은 경우를 살펴보겠습니다.
왼쪽의 배열은 정렬된 배열이기 때문에 만약 우리가 찾고자 하는 값인 target 이 1) 중간 값보다 작고, 2) 0 번째 요소보다 큰 경우를 기준으로 삼을 수 있겠네요. 우선 두 조건이 ~하고 또 ~한 경우, 다시 말해 && 조건이라는 걸 먼저 이해한 채로, 예시와 함께 보충 설명을 진행하겠습니다.
let b = [2, 3, 4, 5, 6, 0, 1]
let target = 4예를 들어 위처럼 b라는 배열이 있고 4를 찾아야 한다고 할 때, 4는 1) 중간 값(===5)보다 작고 2) 0 번째 요소(===2)보다는 크죠. 조건 1. 에서 왼쪽이 정렬되어 있다는 걸 알 수 있기 때문에 이 경우 왼쪽 배열에서 원하는 값을 탐색하면 됩니다.
만약 target 이 0 이라면 어떤가요? 0 은 중간 값인 5보다 작기 때문에 1) 의 조건을 충족하지만 0 번째 요소인 2보다 작기 때문에 2) 의 조건은 충족하지 않습니다. 이 경우에는 오른쪽의 배열이 정렬되지 않았음에도 오른쪽을 확인해봐야 한다는 것을 알 수 있습니다.
사실 target 이 0 번째 요소보다 작다면 첫 번째 조건 에 의해서 당연히 중간 값보다 작게 되고, target 이 중간 값보다 큰 경우에는 마찬가지로 0 번째 요소보다도 크게 됩니다. 두 조건이 다 false 인 경우(중간 값보다 크면서 0 번째 요소보다 작은 경우)는 애초에 성립이 불가능하구요. 따라서 이 경우에는 모든 오른쪽을 확인해보면 됩니다.
여기까지 진행되었다면 반대의 경우도 접근 방식이 크게 다르지 않다는 것을 알 수 있습니다. 0 번째 요소가 중간 값보다 큰 경우이겠네요. 이 경우 위에서 살펴보았듯이 오른쪽의 배열이 정렬된 배열이라는 것을 알 수 있습니다. 찾고자 하는 값이 1) 중간 값보다 크고, 2) 마지막 요소보다는 작을 때가 두 번째 조건이 되겠죠. 이를 만족할 때, 우리가 찾으려는 값은 오른쪽의 정렬된 배열 중에 있어야 한다는 것을 추측해볼 수 있습니다.
let a = [5, 6, 0, 1, 2, 3, 4]
let target = 5위에 주어진 배열을 예시로 살펴보면, 앞에서와 마찬가지로 중간 값보다 작다면 당연히 0번째 요소보다도 작게 됩니다. 반대로 마지막 요소보다 크다면 당연히 중간 값보다 크게 되구요. 두 조건이 다 false 인 경우가 성립할 수 없는 것도 바로 이해하실 수 있을 겁니다.
응용 부분에서 다룬 것은 실제 문제이기 때문에 코드를 다 적는 대신 이렇게 풀이 과정을 조금 세세하게 적어보았습니다. 레퍼런스 코드의 내용을 말로 적은 수도코드라고 봐도 무방하기 때문에 레퍼런스 코드가 혹시라도 이해가 되지 않으셨다면 도움이 될 수 있기를 바랍니다.
