[ 자바스크립트(JavaScript) ] section07 - 11 - 뮤직비디오(결정 알고리즘)

📍 section07 - 11 - 뮤직비디오(결정 알고리즘)

이분탐색 알고리즘을 응용해서 푸는 문제다. 보통 이분탐색을 이용한 문제는 파라메트릭서치(Parametric Search) 알고리즘의 방법으로 풀게 되는데, 이는 값의 최댓값 혹은 최솟값을 구하여 결정문제로 바꾸어 풀 수 있다. 결정 알고리즘과 같은 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 경우가 많으므로 탐색 범위가 20,000,000(이천만)을 넘어가면 이진 탐색으로 접근해보자. 범위가 10,000,000(천만) 이상으로 넘어가면 이진 탐색처럼 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 풀 수 있는 경우가 많다.

 

파라메트릭 서치의 주요 특징은 범위 내에서 조건을 만족하는 값이 있더라도 거기서 끝나는 것이 아니라 그것보다 더 좋은 최적의 답이 있는지 탐색한다는 것이다. 미세한 팁💡 을 말하자면 조건을 흑백논리(?)로 떠올리면 쉽게 풀 수 있다. 예를 들어 나이가 입력된 배열이 오름차순으로 정렬되어 있을 때 19살 보다 크지만 19살과 제일 가까운 사람을 찾는다고 가정해보자. 다음 사진처럼 현재 mid값이 target보다 왼쪽에 있으면 mid의 좌측은 답이 될 수 없다는 결론이 나온다. 그렇기 때문에 mid를 우측으로 이동하여 탐색을 계속하다 보면 최적의 답을 찾을 수 있다.

 

 

자, 이제 문제를 풀어보자.

 

문제: DVD 녹화 시에는 순서가 그대로 유지되어야 한다. 1번 노래와 5번 노래를 같은 DVD 에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화되어야 한다. 한 노래를 쪼개서 두 개의 DVD로 녹화할 수 없다. M개의 DVD에 모든 동영상을 녹화하기로 했다. DVD의 크기를 최소로 하려고 한다. M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 하자.

 

문제의 설명이 조금 어려울 수 있지만 결론적으로 M개의 DVD에 음악을 모두 같은 크기로 담아야 하는데, 그 크기가 가장 최소가 되는 값을 찾는 문제다. 최적의 값을 찾아야 하기 때문에 이분 탐색을 이용한 파라메트릭 서치 알고리즘을 사용하면 된다. 여기서 lt는 주어진 값의 제일 작은 값(1) 혹은 제일 큰 값(9)을 선언할 수 있는데, 1은 최적의 답과 근접하지 않으므로 제일 큰 값인 9를 주었다. rt는 arr을 모두 더한 값을 줬는데, 이는 한 DVD에 저장할 수 있는 음악의 크기를 모두 더한 값이다. 혹은 부른 곡의 길이가 10,000분 이하이므로 최대로 나올 수 있는 값인 n*10000을 줘도 된다. 지금까지 읽은 내용이 잘 이해가 되지 않으면 다음의 풀이과정을 살펴보자.

 

 

728x90

let n = 9;
let m = 3;
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

console.log(solution(n, m, arr));
// let rt = n * 10_000;

function solution(n, m, arr){
    let lt = Math.max(...arr);
    let rt = 45;
    let answer;

    while (lt<=rt){
        let mid = Math.floor((lt+rt)/2);
        console.log(`lt=${lt}, rt=${rt}, mid=${mid}`)
        let cnt=1;
        let sum=0;

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

        if (cnt <= m) answer=mid, rt=mid-1;
        else lt=mid+1;
    }
    console.log(answer)
}