이진탐색 알고리즘

세나정·2023년 5월 9일

[동빈나 JS 코딩테스트]

목록 보기

3/8

팁! 항상 문제에서 범위가 몇십억처럼 크게 주어질 땐 이진탐색을 쓰는 것인지 의심 해보면 됨

예산

풀이

function solution(n)
{
    let arr = [120, 110, 140, 150]
    let m = 485
    
    let ans = 0;
    
    let start = 1;
    let end = Math.max(...arr) // 배열 중 최댓값
    
    while (start <= end) {
        let mid = parseInt( (start + end)/2 ) // 시작값 + 끝값으로 mid 설정
        let total = 0; // 예산의 총액
        
        for (x of arr) { // 예산을 한 개씩 확인하여 배정
            total += Math.min(mid, x) // mid값과 배열의 인덱스 중 작은 값을 total에 더해줌
        }
        
        if ( total <= m) { // 예산이 아직 갖고 있는 돈보다 적다면 한번더, 대신 start의 값을 mid+1로
            ans = mid;
            start = mid+1
        } else {
            end = mid-1 // 예산의 총합이 갖고 있는 돈보다 커졌다면 값을 줄여나감
        }
    }
    
    console.log(ans)
}

나무 자르기

풀이

function solution(n)
{
    let arr = [20, 15, 10, 17]
    let m = 7
    
    let 절단기높이 = 0;
    let start = 1;
    let end = Math.max(...arr)
    
    while (start <= end) {
        let mid = parseInt((start+end)/2)
        let tree = 0; 
        
        for (v of arr) {
            if (v > mid) {
                tree += v - mid;
            }
        }
        
        if (tree < m) { // 나무의 양이 부족하다면 더 많이 자르기
            end = mid - 1;
        } else { // 나무의 양이 충분하다면 덜 자르기 (절단기 높이 키우기)
            절단기높이 = mid;
            start = mid + 1;
        }
    }
    
    // 높이 
    console.log(절단기높이)
}

설명

우선 줄여나가는 것이고 절단기의 높이를 조절해야 하는 문제기 때문에 이진탐색의 로직을 알더라도 이해하는데에 조금 오래걸릴 수 있다. 천천히 해보면서 감을 익혀야한다.

1회차 | while(1<=20)
mid = start+end -> 1+20 -> [10]
for문 tree (나무길이) = 20>10 : 10, 15>10 : 5, 10>10 : X, 17>10 : 7 -> [22]
tree(22)가 m(7)보다 작은 조건문에 속하지 않으므로 else문으로 이동
절단기 높이 = [10]
start = [11]

2회차 | while(11<=20)
mid = 11+20 -> [15]
for문 tree = 20 > 15 : 5, 15 > 15 : X, 10 > 15 : X, 17 > 15 : 2 -> [7]
tree(7)이 m(7)보다 작은 조건문에 속하지 않으므로 다시 한번 더 else문으로 이동 
절단기 높이 = [15]
start = [16] // ★ 여기서 start 값이 16임에 집중 ★

3회차 | while(16<=20)
mid -> 16+20 -> [18]
for문 tree = 20 > 18 : 2, X, X, X -> [2]
tree(2)가 m(7)보다 작으므로 if문에 속함
절단기 높이 = 아직 [15]
end = mid - 1 = 18-1 -> [17]

4회차 | while(16<=17) 
mid -> 16+17 -> [16]
for문 tree = 20 > 16 : 4, X, X, 17 > 16 : 1 -> [5]
절단기 높이 = 여전히 [15]
tree(5)가 m(7)보다 작으므므로 if문에 속함
end = 16 - 1 -> [15] 

★ 여기에서 end가 start보다 커졌으므로 while문을 돌 수 없어서 
그대로 절단기 값에 남아있던 15가 리턴

랜선 자르기

풀이

function solution(n)
{
    let arr = [802, 743, 457, 539]
    let m = 11
    // 답 : 200 -----------------
    
    let start = 1;
    let end = Math.max(...arr) 
    
    let 랜선길이 = 0;
    
    while (start <= end) {
        let mid = parseInt((start+end)/2) 
        let cnt = 0; 
        
        for (v of arr) { // 400 | 200 
            cnt += parseInt(v / mid)
        }
        
        if (cnt < m) {  // 갯수가 부족하다 너무 크게 잘랐다
            end = mid-1 // end값을 mid-1 즉, 이제 왼쪽만 봄 (더 작게 자르려고)
        } else {
            // 갯수가 너무 많다, 너무 작게 잘랐다
            랜선길이 = mid // ★ 우선 그떄에 값을 mid에 저장 (while문 못 들어갈 수도 있으니)
            start = mid + 1 // start를 mid+1 즉, 이제 오른쪽만 봄 (더 크게 자르려고)
        }
    }
    
    console.log(랜선길이)
}