"끈끈하게 버텨내기"
이진 탐색 (Binary Search)
이진 탐색은 주어진 탐색 구간을 절반씩 나누어가며 원하는 값을 찾아가는 탐색 알고리즘입니다. 기본적으로 배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있는 알고리즘이죠.
만약 이미 정렬되어 있는 두 개의 배열을 주고서, 이 두 배열에서 n 번째 요소를 찾아야 한다면 어떨까요? 이진 탐색의 응용편이라고 할 수 있는데 막상 이해가 안 되어서 이해해보려고 블로깅을 시도하게 되었습니다.
예시를 통한 문제 이해
두 개의 배열이 주어졌고, 이 두 배열은 이미 정렬이 되어있는 배열입니다. 기본적으로 이 두 배열은 자연수로 이루어져 있다고 할 때, n 번째 자연수는 무엇일까요?
첫 번째 배열이 arr1 = [2, 4, 7, 8] 이고, 두 번째 배열이 arr2 = [1, 3, 5, 6] 이라고 해봅시다. 이 중에 5 번째 자연수를 찾아야 한다고 할 때 어떤 접근을 할 수 있을까요?
이정도 크기의 배열은 순차적으로 검색해도 금방 답이 나올 수 있지만, 알고리즘 문제는 늘 배열이 더 커질 경우를 가정해서 풀어나가야 합니다. 따라서 이진 탐색을 활용할 수 있는 방법을 찾아봐야 할 것 같습니다.
배열의 크기가 커질수록 두 배열의 요소들이 고르게 분포되어 있다고 생각해본다면, 주어진 n 이라는 자연수를 반으로 쪼개어볼 수 있을 겁니다. 5 를 반으로 쪼갠다고 하면 2.5 가 되죠. 올림하면 3 이 되니 3 번째 요소를 찾아보도록 하겠습니다.
arr1 의 3 번째 요소는 arr1[2] === 7입니다. arr2 의 3 번째 요소는 arr2[3] === 5죠. 두 요소를 비교하면 5 가 더 작은 값입니다. 이 경우, 최소한 arr2[3] === 5 를 포함해서 그 이전의 값들을 다 제외해도 된다는 것을 알 수 있습니다. 배열이 이미 정렬이 되어 있고, 두 배열의 3 번째 요소 값을 서로 비교했기 때문이죠.
이제 arr2 에는 6 하나만 남아있습니다. arr1 에는 여전히 배열 전체가 남아있겠죠. n === 3 까지의 값을 확인한 셈이니 이제 5 - 3 = 2 만큼을 확인해보면 될 것 같습니다.
(만약 어느 하나의 배열이 위의 과정에서 다 제거된다면, 그 다음부터는 다른 하나의 배열에서만 값을 찾으면 됩니다.)
다시 한번 2 를 반으로 쪼개고 올림합니다. 그러면 1 이 되겠죠. arr1[0] === 2 이고 arr2[0] === 6 가 됩니다. 이번에는 2 를 제외해야겠군요.
남은 n 값이 1 이니 반으로 쪼개어 올려도 1 이 됩니다. arr1 에서 4 를 제외하고 나면, 이제 5번째 자연수까지를 다 찾아낸 셈이 되었습니다.
이제 이를 기반으로 코드를 작성하면 될 것 같습니다.
문제는 지금처럼 배열 자체를 변형하게 되면, 예시에서 5 번째 자연수인 5가 첫번째 과정에서 제거가 된다는 점입니다. 이런 점을 방지하기 위해서는 배열 자체를 바꾸기보다는 인덱스를 늘리는 방식으로 접근해야 할 것 같네요.
이해를 마치고 나면 코드를 작성해보자
코드까지 블로깅 하지는 않을 생각입니다. 다만 알고리즘은 결국 코드를 직접 작성해봐야 하는 것이기 때문에 꼭 코드를 작성해서 돌려보면서 검토해보면 좋을 것 같습니다.
