이진 탐색 알고리즘 (Binary search Algorithm)

 

이진 탐색 알고리즘(이분 탐색 알고리즘)은 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘이다. 맨 처음 단계에서 정렬된 배열의 중간의 값을 임의의 값으로 선택한다. 선택한 임의의 값과 찾고자 하는 값의 크고 작음을 비교하여 탐색하는 방식이다. 만약 임의의 값이 찾는 값보다 클 경우, 임의의 값은 새로운 최댓값이 된다. 반대로 임의의 값이 찾는 값보다 작으면 해당 값은 새로운 최솟값이 된다. 

 

https://mikebuss.com/2016/04/21/binary-search/

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있으나, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다(O(l ogN)). 

BinarySearch(A[0..N-1], value, low, high) {
  if (high <= low)
    return -1 // not found
  mid = (low + high) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
  else
    return mid // found
}

 

프로그래머스 입국심사 문제를 통해 이분 탐색 연습을 해보자. https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

우선 내가 푼 방식은 아래와 같다. 다만 이렇게 푼다면 시간이 가장 적게 걸리는 경우를 찾지 못한다. 예를 들어 6명이 대기하고 있고 심사대는 [6, 10]이라면, 24초 ~ 26초 사이에 6명이 검사 가능한데, 답은 24가 아닌 26으로 나와버린다.

function solution(n, times) {
    times.sort((a, b) => a - b);
    let answer = 0, min = 1, max = times[times.length - 1] * n;
    
    while(1){
        let mid = Math.floor((max + min) / 2);
        let total = 0;
        for(let i = 0; i < times.length; i++){
            total += Math.floor(mid / times[i]);
            if(total === n){
                answer = mid;
                return answer;
            }
        }
        if(total > n){
            max = mid - 1;
        }else if(total < n){
            min = mid + 1;
        }
    }

    return answer;
}

 

이 문제는 모든 인원을 검사할 때 걸리는 시간 중에서 가장 빠른 시간을 탐색하는 방식으로 해결해야된다. times을 오름차순으로 정렬한 뒤,  마지막 요소와 n을 곱하여 이를 max로 둔다 (n명을 검사할 때 최대로 걸리는 시간은 검사시간이 가장 오래 걸리는 검사대에 모든 인원 n명이 몰리는 경우이다). min은 최소값이라고 생각할 수 있으나 사실 이는 최소값이 아닌 n명을 모두 검사할 수 없는 시간이다. 어쨌거나 min과 max를 구했다면 이 두 값의 중간 값(pivot)을 알 수 있다. 이렇게 알게된 시간(pivot)동안 검사대에서 몇 명을 검사할 수 있을지 확인한다. 만약 검사할 수 있는 인원이 n명을 초과한다면 시간을 더 줄이는게 가능하다는 의미이다. max를 pivot -1로 변경한 후 이것과 min 사이의 중간 값을 구한다. 이러한 과정을 반복하며 max와 min값이 동일해질 때까지 반복한다.

function solution(n, times) {
    // 이분탐색은 정렬이 우선되어야 한다.
    times.sort((a,b) => a - b);
    
    let min = 1, max = times[times.length - 1] * n;
    let result = max;
    
    while (max >= min) {
        // min과 max의 중간값(pivot)을 구한다.
        let pivot = Math.floor((min + max) / 2);
        // pivot동안 몇명을 검사할 수 있는지 확인한다.
        let pass = times.reduce((acc, curr) => {
            let tot = Math.floor(pivot/curr);
            return acc + tot;
        }, 0);
        
        if (pass >= n) {
            // 검사 가능한 인원이 실제인원 이상이면 max와 result를 수정.
            max = pivot - 1;
            result = Math.min(result, pivot);
        } else {
            // 검사 가능한 인원이 실제인원 미만이면 min을 수정.
            min = pivot + 1;
        };
    };
    
    return result;
}

 

 

 

 

---

참고 자료

• https://codingjuny.tistory.com/24
• https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98