알고리즘 | 이분탐색 개념과 예제 + 심화

📌 개념 다지기

이분 탐색

탐색 기법중 하나로, 탐색하고 싶은 범위를 두 부분으로 분할해서 찾는 방법이다.

두 부분으로 계속 분할해서 조건에 맞는지 찾아가기 때문에, 시간 복잡도가 O(log n)으로 매우 빠른편이다.

 

✔️탐색하는 방법

1. 배열이 정렬(sort)되어 있어야한다.
2. left와 right를 배열의 양 끝으로 설정한다.
3. mid = (left + right) / 2 로 설정하여, mid 값이 기준값보다 작거나 큰지 확인한다.
   1. (오름차 배열 정렬되어있을 때) mid 값이 기준값 보다 작다면, left를 (mid+1)로 설정한다. 
   2. (오름차 배열 정렬되어있을 때) mid 값이 기준값 보다 크다면, right를 (mid-1)로 설정한다.
4. left > right 가 될 때 까지 2,3 번을 반복한다.

---

✏️이분 탐색 예제1

임의의 N개의 숫자가 입력으로 주어졌을 때, N개 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어진다면, 

이분 탐색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성해라. 중복값은 존재하지 않는다.

 

• 입력값 
  • nums : N(3<=N<=1,000,000)개의 수열 
  • m : 숫자 M
• 출력값
  • 정렬한 뒤 M의 인덱스 값
• 입력 예시 : [23, 87, 65, 12, 57, 32, 99, 81], 32
• 출력 예시 : 3

 function solution(nums, m) {
    let n = nums.length;
    // 오름차순 정렬
    nums.sort((a, b) => a - b); 

	// left, right로 배열을 탐색
    let lt = 0,
      rt = n - 1;
      
    // lt > rt일 때 탈출
    while (lt <= rt) { 
    // mid값 설정
      let mid = Math.floor((lt + rt) / 2);

	// m과 비교하여 lt와 rt 변경. m과 동일하면 그때 mid가 정답임!
      if (nums[mid] < m) {
        lt = mid + 1;
      } else if (nums[mid] > m) {
        rt = mid - 1;
      } else {
        return mid;
      }
    }
 }
  console.log(solution([23, 87, 65, 12, 57, 32, 99, 81], 32)); // 정답 2

 

---

📌심화 하기

 

✏️이분 탐색 예제2

엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다.

선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.

예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.

그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자.

N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

입력	매개변수 nums에 K개의 각 랜선의 길이가 주어집니다. 각 랜선의 길이는 1,000,000 이하이다. 매개변수 n에 N이 주어집니다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다.	[802, 743, 457, 539], 11
출력	N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 반환합니다.	200

 

✔️입출력 분석

입력이 nums = [802, 743, 457, 539], n = 11 일 때,

nums에 들어있는 랜선들을 가지고 11개의 같은 길이의 랜선을 만들려고 할 때, 만들 수 있는 최대 랜선 길이를 구해야 한다.

최대 랜선의 길이는 200으로, 

802 = 200 + 200 + 200 + 200 + 2

743 = 200 + 200 + 200 + 143

457 = 200 + 200 + 57

539 = 200 + 200 + 139

일 때, 길이 200의 랜선이 11개로 n값을 만족하므로 정답이다. 

 

✔️문제 분석

최대 랜선 길이는 nums에 K개의 랜선 길이가 주어질 때, 가장 긴 랜선의 길이를 넘을 수 없다.

즉, 위의 예제에서는 1 ~ 802 사이의 값이 자를 수 있는 랜선 길이가 될 수 있으므로, 그 사이에서 정답이 나온다.

따라서 1 ~ 802 사이의 값을 이분탐색으로 돌면서 m 값을 만족시킬 수 있는지 확인하면 된다.

 

그럼 nums배열에 있는 최대값을 꼭 찾아야 할까?

아니다. 랜선의 길이는 1,000,000이 최대이므로, 최대 랜선 길이는 1 ~ 1,000,000 사이에 존재한다.

이분탐색의 시간복잡도는 O(log n)이므로, log 1,000,000 == log 2^20 == 20 번만 탐색하면 된다.

 

따라서 20번 탐색하면서, mid값으로 m개의 랜선을 만들 수 있는지 확인하는 함수를 잘 작성해야 한다.

풀이 코드는 다음을 참고하자.

 

 

 // 조건을 만족하는지 확인하는 함수
  function cntNum(x, nums) {
    let result = 0;

    // 길이 x로 랜선을 잘라서 만들 수 있는 랜선의 갯수를 구함
    for (let i of nums) {
      result += parseInt(i / x);
    }
    return result;
  }
  function solution(nums, n) {
    // 랜선의 최대길이가 1000000이므로, 그 사이 안에서 정답이 나온다. => 이분탐색
    let lt = 0,
      rt = 1000000;
    let answer;

    while (lt <= rt) {
      let mid = Math.floor((lt + rt) / 2);
      let cnt = cntNum(mid, nums); // 조건을 만족하는지 확인하는 함수.

      if (cnt >= n) {
        answer = mid;
        lt = mid + 1;
      } else if (cnt < n) {
        rt = mid - 1;
      }
    }
    return answer;
  }
  console.log(solution([802, 743, 457, 539], 11)); // 200