결정 알고리즘(이분검색) - 뮤직비디오

결정 알고리즘은 답을 정하고 이 답이 유효한지 확인하면서 더 좋은 답을 찾아가는 방식을 의미한다.

주로 이분 검색을 사용한다.

 

📝풀이과정

먼저 문제에 대한 정확한 이해가 필요하다. 이 문제는 더더욱 그렇다.

문제에 대한 이해가 부족하면 알고리즘을 적용하는 데 왜 이렇게 적용하는지 어려움을 겪는다.

 

먼저 곡의 길이가 분 단위로 다음과 같이 주어진다.

1 2 3 4 5 6 7 8 9

 

그리고 M개의 DVD 갯수가 주어진다.

3

 

DVD의 최소 용량의 크기를 구해야한다. 

만일 용량의 크기가 30이라고 해보자. 담을 수 있는 최대 크기가 30이므로 다음과 같이 담길 것이다.

[ 1 2 3 4 5 6 7 ]  [ 8 9 ]

이렇게 총 2개의 DVD를 사용해서 담을 수 있다. 우리는 3개의 DVD에 담아야하므로 용량을 더 줄일 수 있다.

 

그렇다면 용량의 크기가 15라고 해보자.

[ 1 2 3 4 5 ]  [ 6 7 ]  [ 8 ]  [ 9 ]

이러면 4개의 DVD에 담기게 된다. DVD의 용량이 적은 것이다. DVD의 용량을 늘려서 3개의 DVD에 담기도록 해야한다.

 

정리를 하면 DVD의 용량을 정하고 모든 곡을 담는데 필요한 DVD의 갯수를 구한다.

그 갯수가 M보다 크다는 것은 용량을 늘려야하는 것이고, M보다 작은 것은 용량을 더 줄여야한다는 것이다.

우리는 M개에 담을 수 있는 최소 용량의 크기를 구해야하기 때문이다.

이 때 DVD의 용량을 정하는 방법을 이분탐색을 통해 구현할 수 있다. 이분탐색을 하며 최적의 결과값을 찾아가는 것이다.

---

먼저 곡을 담을 수 있는 최소,최대의 DVD 용량을 계산한다.

위의 예제에서는 DVD 용량이 9라면 모든 곡을 담을 수 있는 최소의 용량이고 모든 곡의 길이를 더한 45가 최대 용량이다.

사실 최소용량과 최대용량은 적당히 작게 크게 잡아도 된다. 이분탐색을 이용할 것이기 때문에 탐색할 데이터가 크게 줄어들기 때문이다.

 

min = 9, max = 45

 

이제 이분탐색을 통해 최적의 DVD 용량을 구해보자.

 

중간값인 27부터 시작한다. 용량이 27일 때 곡들을 담는다면 몇 개의 DVD가 필요한 지 구한다.

용량이 27인 경우에는 2개의 DVD가 필요하다. 우리는 3개의 DVD에 담아야하므로 DVD 용량을 더 줄여야한다.

그렇다면 max를 중간값-1에 위치시켜 다시 재탐색한다.

 

min = 9, max = 26

 

이제 중간값은 17이 된다. 17일 때는 3개의 DVD가 필요하다.

우리가 찾고자하는 3개의 DVD는 맞지만 최소 용량인지는 더 탐색해야한다. 17보다 용량이 작을 경우에도 3개의 DVD가 필요할 수 있기 때문이다.

그렇기 때문에 이제는 찾고자 하는 용량의 범위를 17보다 작은 범위에서 찾아야한다. 때문에 max 값을 중간값-1 위치로 이동한다.

 

min = 9, max = 16

 

이렇게 위의 과정을 반복했을 때 나오는 결과값을 반환하면 된다.

---

🛠구현

구현할 때 까다로웠던 부분은 곡의 길이 데이터를 용량에 맞게 자르는 과정이었다.

즉, 용량이 17일 때는 곡의 길이 데이터를 하나씩 더해가면서 17을 넘게되면 잘라야한다.

function solution(m, arr) {
  let lt = Math.max(...arr);
  let rt = arr.reduce((acc, cur) => acc + cur, 0);
  let result = -1;

  while (lt <= rt) {
    let cnt = 0;
    let mid = parseInt((lt + rt) / 2);
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
      sum += arr[i];
      if (sum + arr[i + 1] > mid) {
        sum = 0;
        cnt += 1;
      }
      if (sum <= mid && i === arr.length - 1) cnt += 1;
    }
    if (cnt <= m) {
      result = mid;
      rt = mid - 1;
    } else lt = mid + 1;
  }

  return result;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(solution(3, arr));

 

[1 2 3 4 5 6 7 8 9] 라면 sum에 요소를 차례대로 더해준다.

더한 요소의 다음 요소를 더했을 때 중간값보다 크다면 지금 더한 요소까지가 용량에 넣을 수 있는 것이다.

따라서 DVD의 갯수를 하나 들리고 sum을 초기화했다.

 

if (sum <= mid && i === arr.length - 1) cnt += 1;

 

처음에는 위의 조건을 적지 않았다.

이 조건을 적지 않으니 맨 마지막 요소를 순회할 때 다음 요소가 존재하지 않으니 DVD의 갯수를 세어야함에도 세지 않고 반복문을 빠져나오는 것이었다. 때문에 위의 조건을 추가했다.

 

테스트 케이스는 통과했지만 더 다양한 테스트에서 확인하기 어려웠고, 또한 어딘가 모르게 코드를 비효율적으로 구현했다는 느낌을 받았다. 그래서 강의를 보며 까다로움을 느낀 부분을 해소하기로 했다.

---

function count(songs, capacity) {
  let cnt = 1,
    sum = 0;
  for (let x of songs) {
    if (sum + x > capacity) {
      cnt++;
      sum = x;
    } else sum += x;
  }
  return cnt;
}

function solution(m, songs) {
  let answer;
  let lt = Math.max(...songs);
  let rt = songs.reduce((a, b) => a + b, 0);
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(songs, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }
  return answer;
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(solution(3, arr));

function count(songs, capacity) {
  let cnt = 1,
    sum = 0;
  for (let x of songs) {
    if (sum + x > capacity) {
      cnt++;
      sum = x;
    } else sum += x;
  }
  return cnt;
}

 

살펴볼 부분은 count 함수이다. 강사님도 이 부분이 핵심이라고 하셨다.

cnt가 1이 되는 이유는 cnt가 DVD의 갯수이기 때문이다. 우선 곡을 담으려면 최소 1개의 DVD는 필요하기 때문에 1로 초기화했다. 그런다음 sum에 요소를 더했을 때 용량을 초과한다면 해당 요소는 더 담을 수 없기 때문에 다음 DVD에 담아준다.

내가 작성한 코드보다 직관적인 이해가 빠르고 훨씬 깔끔하다.

 

😊느낀점

도저히 문제 풀이의 방향이 잡히지 않았다. 마치 스택을 활용한 쇠막대기 문제와 비슷했다. 쇠막대기 문제도 보자마자 어떻게 풀어야되는지 감조차 잡히지 않았다.

우선은 문제를 완벽하게 분석하고 스스로 이해하는 과정이 중요함을 느꼈다. 

그리고 풀이과정이 납득이 되어야한다. 대충 이렇게 하면 되겠지라고 바로 구현으로 넘어가면 더 꼬여서 다시 생각해야했다. 시간도 더 많이 소요된다.

정리하면 DVD의 최소 용량의 값을 정하고 조건에 맞는지 반복 탐색하는 것이다. 비슷한 유형의 문제가 나오면 결정 알고리즘을 사용할 수 있는지 적극적인 시도를 해야겠다.