이분 탐색과 결정 알고리즘

이분 탐색(Binary Search)

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• left(start) , mid, right(end), 3가지 변술르 이용하여 원하는 데이터를 찾는다.
• O(logN)의 시간복잡도를 가진다.

코드

• 자바스크립트를 이용한 구현

function BinartSearch(target, arr) {
  let answer;
  arr.sort((a, b) => a - b);
  let lt = 0; // start
  let rt = arr.length - 1; // end
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2); // mid
    if (arr[mid] === target) {
      // target : 찾고자 하는 값
      answer = mid + 1;
      break;
    } else if (arr[mid] > target) {
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }

  return answer;
}

결정 알고리즘

• Parametric Search(파라메트릭 서치)
• 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다.
• 이진탐색에 사용했던 패턴을 기반으로 한다.

예제1)

길이가 N인 숫자 리스트가 있다고 가정했을때, 총 T 개의 그룹으로 리스트를 나눠야 한다.
T개의 그룹으로 리스트를 나눴을때 한 그룹당 최소 얼마의 숫자합이여야 하는지 구하시오.

// 카운트, 몇 개의 그룹으로 나뉘는지 확인.
function count(numList, mid) {
  let count = 1;
  let sum = 0;
  for (let x of numList) {
    if (sum + x > mid) {
      count++;
      sum = x;
    } else {
      sum += x;
    }
  }
  return count;
}
// 메인 솔루션
function decision(numList, target) {
  let answer;
  let lt = Math.max(...numList); 
  let rt = numList.reduce((a, c) => a + c, 0); 
  // 이진 탐색 패턴
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    // 숫자 합이 mid일 때 나오는 갯수
    if (count(numList, mid) <= target) {
      answer = mid; 
      rt = mid - 1; 
    } else {
      lt = mid + 1; 
    }
  }
  return answer;
}

결정 알고리즘은 보통 이진탐색하는 부분과 count하는 부분으로 나눠는 패턴을 보인다.

이진 탐색을 이용해 mid값을 정한다. 이 mid값의 의미는 숫자 합의 capacity를 나타내고 이 capacity로 나올 수 있는 그룹의 갯수를 구하는 것이 count함수이다.

count함수의 리턴 값이 target 이하라면 answer가 될 조건을 만족한 것. 허나 이것이 최적의 해인지는 알 수 없다. while문을 끝까지 돌고나면 최적의 결과물이 나올 것이다.

TIP

답이 될 수 있는 조건을 먼저 파악하자.
숫자 그룹의 수가 target보다 작아야한다.
mid값 증가 또는 감소에 따라 count값이 어떻게 되는지 파악하자.
위 문제의 경우 mid값이 증가하면 count는 줄어든다. 그럼 count를 늘리고 싶으면 mid를 줄이고 count를 줄이고 싶으면 mid를 늘리면 된다.

=> 위 두가지 조건을 먼저 파악하면 이진탐색 패턴의 결정 알고리즘을 정하기 쉬워진다.