[자바스크립트, JS] 이분 검색(Binary Search), 결정 알고리즘 문제 풀이, 개념 정리

📋 글 작성 배경

최근 자바스크립트로 코딩테스트 공부를 하고 있다. 알고리즘이라하기에도 민망한 문제들을 풀고 있었는데, 이제 조금 알고리즘스러운 문제를 풀고 이해하는 노력 중인 것 같다. 문제는 이분 검색을 통한 결정 알고리즘이다. 문제의 이름은 "뮤직비디오"이고 구글링을 한번 해봤을 때 꽤나 유명한 문제같다. 나는 이 문제를 인프런 코테강의에서 발췌해서 공부의 목적으로 블로그에 정리할 예정이다.

📝 문제 소개

결정 알고리즘을 소개할 예정인데, 문제를 먼저 확인하고, 해결방안으로 알고리즘으로 소개하는 순서로 진행해야겠다.

문제는 다음과 같다.

문제
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의DVD는모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

입력 예제
3, [1, 2, 3, 4, 5, 6, 7, 8, 9]

출력 예제
17

문제를 간략하게 정리를 해보면, 나눠야할 DVD의 개수를 M, 각 노래의 길이가 배열로 차례대로 넘어온다. 예시를 보면, 1분부터 9분까지 9개의 곡을 순서를 유지하여, 3개의 DVD로 잘라서 녹화해야한다. 이 DVD의 길이는 최소의 용량으로 지정하는 것이 좋으니, 노래를 자르지 않고, 9개의 곡을 3개의 DVD에 효율적으로 담으라는 말이다.

📝 어떻게 풀 것인가?

먼저 문제를 해결하기 위해서는, 우리가 얻고자 하는 값의 범위를 지정해야한다. 결정알고리즘이 그렇다. DVD의 최소 길이는 9가 되겠고 최대길이는 45가 되겠구나.(하나만 담기는 경우와 모두 담기는 경우를 생각했다. 값의 범위는 9 <= X <= 45 이구나. 이젠 이분 탐색을 통해 우리가 원하는 조건에 해당하는 값중에 최소값을 찾아보자.
이분 탐색은 중간 값을 정해서 계속 쪼개어 들어가는 상황을 만들어야한다. 따라서 값의 범위를 변수로 할당해두고, 그 가운데에 해당하는 변수도 만들어서 범위를 좁혀가는 활동을 해야한다. 그리고 가운데에 해당하는 값으로 유효한지를 테스트해보면된다.

📝 솔루션 코드

개념 이해와 정리를 목적으로한 포스팅이므로 코드와 설명이 불친절해도 이해바란다. 문제 해결 코드를 소개하겠다.

const count = (arr, capacity) => { // DVD개수를 세어주는 함수
  let cnt = 1; // dvd 한장 있음
  let hap = 0;

  for (let x of arr) {
    if (hap + x > capacity) {
      cnt++;
      hap = x;
    } else hap += x;
  }

  return cnt;
};

const solution = (m, arr) => {
  let answer = 0;

  let lt = Math.max(...arr);
  let rt = arr.reduce((a, b) => a + b);

  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(arr, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    } else lt = mid + 1;
  }

  return answer;
};

console.log(solution(3, [1, 2, 3, 4, 5, 6, 7, 8, 9])); // output: 17

코드설명을 간략하게 하면서 정리를 마치겠다.

먼저, solution 함수에 테스트 변수들을 넘겨주고, answer은 우리가 정답으로 return 할 값이다. 값의 범위를 먼저 지정해야한다했으니, lt와 rt의 변수 값들을 지정했다.

그리고 while문을 돌리는데, 조건은 lt보다 rt가 앞으로 넘어오거나, rt보다 lt가 뒤로 넘어오는 순간일 것이다. 그렇게 되면 모든 탐색이 종료되었음을 의미하기 때문이다.
그리고, 그 범위의 중간값인 mid를 설정한다. 이분탐색은 중간지점으로 잘라가면서 탐색을 하기때문에 효율이 좋은 것이다. 그리고 arr와 mid를 count함수에 보낸다. count함수는 mid로 넘어온 값을 DVD길이로 arr를 몇개를 자를 수 있는지 유효성을 검사해주는 함수라고 생각하면 된다. arr 배열에 있는 곡들을 hap이라는 변수에 하나씩 더하면서 길이가 mid만큼 채워가다가 mid보다 값이 커지는 순간 cnt를 증가시켜주고 hap을 그 순간 x의 값으로 초기화를 한다. 그 방식을 if, else로 표현했다. 한 곡씩 넣을때부터 이미 DVD의 개수가 카운트 되는 것이니 cnt를 1로 두는 것이다. 그렇게 해서 count함수로 부터 넘어온 return 값이(cnt) 주어진 m의 값(보기에서는 3)보다 작거나 같으면 그 값은 유효한 것이다! 이 말이 중요하다. 작거나 같아야 유효하다! 3개로 자르라 했는데 1개나 2개로 잘라도 된다는 것은 그만큼 길이가 넉넉하다는 말이다. DVD의 길이가 넉넉하니까 무조건 유효한 것이다. 그럼 더 효율적인 길이를 찾기위해 최대값인 rt를 mid -1로 줄이고 다시 검사를 하면된다.

그렇지 않고 주어진 mid의 길이로 유효성 검사를 했을 때 너무 많이 쪼개진다면 길이가 짧다는 것이니 늘려주면된다. mid+1로 lt값을 변경하면된다. 이 과정을 계속 거친다보면 17이라는 값이 나오게된다.

해결하기까지 꽤 복잡하고 여러번 수행하는 것 처럼보이지만 이분등 하면서 탐색을 하기 때문에 모든 경우를 확인하는 것보다 훨씬 효율적이라고 말할 수 있다.

📝 정리하며..

코딩 테스트를 준비하며, 강의를 들으면서 하루에 몇개씩 정해두고 꾸준히 풀어보려고 하고 있는데, 모처럼 이해하기 살짝 어려운 내용이 나와서 정리를 하고 있다. 뒤의 문제인 마굿간이라는 문제도 정리해야하는데 졸려서 큰일이다.