이진 탐색 (이분 탐색) _백준 문제 1920, 10816, 1654 (javascript)

백준 이진 탐색 알고리즘 문제풀이입니다.

이진 탐색이란?

전체 범위를 가운데 기준으로 나누어 두 구간으로 분할해줍니다. 그리고 조건을 만족하는 구간이 어디인지 확인 후 해당 구간을 다시 분할해주는 방식으로 탐색하는 방법입니다. 처음부터 끝까지 탐색하는 것보다 속도가 훨씬 빠르기 때문에 많이 사용되는 방법입니다.

 

1부터 10까지 중에 4를 찾는 예를 들어 이진 탐색을 해보도록 하겠습니다.

 

1. 이진 탐색에서 가장 중요한 것은 우선 값들이 오름차순으로 정렬되어야 한다는 것입니다.

1

2

3

4

5

6

7

8

9

10

2. start, end, mid 값들을 잡아줍니다.

• start = 1
• end = 10
• mid = Math.floor((start+end)/2)

3. target과 mid값을 비교 후 start와 end값의 위치를 조정합니다.

• if(target>mid){start = mid + 1}
• if(target<mid){end = mid -1}
• 예시에서는 target(4)이 mid(5) 보다 작기 때문에 end값이 4가 됩니다.

4. mid값을 다시 계산하여 3의 과정을 반복합니다.

•  mid값과 target값이 동일하거나 start값과 end값이 일치할 때까지 반복합니다.
• 위 예제에서는 start, end, mid값이 모두 4로 일치될 때까지 반복하여 값을 구할 수 있습니다.

---

실제 문제를 풀어보며 이진 탐색 방법을 활용해봅시다.

 

1. 문제 번호 1920

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

const readline = require('readline')
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
})

const binarySearch = (array, target, start, end) => {
    let mid = 0;
    while (start <= end){
        mid = Math.floor((start + end)/2)
        if(array[mid] === target){
            return mid;
        } else if (array[mid]>target){
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    return -1;
}

const solution = (input) => {
    const n = parseInt(input[0]);
    const A = input[1].split(" ").map(e => parseInt(e));
    const m = parseInt(input[2]);
    const B = input[3].split(" ").map(e => parseInt(e));
    let ans = ''

    A.sort((a,b) => a - b) //오름차순
    // console.log("A",A)

    B.forEach(
        (value, idx) => {
            // console.log("value",value, "idx",idx)
            if(binarySearch(A, value, 0, n-1) !== -1){
                ans += (idx === m-1) ? '1' : '1\n'
            }else{
                ans += (idx === m-1) ? '0' : '0\n'
            }
        }
    )

    console.log(ans)
}

const input = [];
rl.on("line", function(line){
    input.push(line);
}).on("close", function(){
    solution(input);
    process.exit();
})

 

2. 문제 번호 10816

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

위의 문제와는 다르게 일치하는 값들이 여러 개 있는 경우 개수를 구하는 문제입니다. 이때는 해당 값의 최소 인덱스와 최대 인덱스를 구하여 총 몇개가 있는지 알 수 있습니다다. 총 개수는 (최대인덱스 - 최소인덱스 + 1)이 됩니다.

 

최소인덱스와 최대인덱스를 구하기 위해선 두 가지 이분 탐색 함수가 필요합니다.

1번 문제에서는 타깃 값과 일치하는 mid값을 찾음과 동시에 return을 했다면 이번에는 mid값을 일단 보관해두고 start와 end의 위치를 한번 더 변경해줍니다.

//해당 숫자가 몇 번 나오는지 count 해야하는 경우, lower index와 upper index를 구한다
//3,4,5 인덱스에서 같은 값이 나오는 경우 lower index = 3, upper index =5 이므로 숫자의 개수는 5-3+1

const readline = require('readline')
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
})

const lower = (array, target, start, end) => {
    let ans = -1;
    while(start<=end){
        mid = Math.floor((start+end)/2)
        if(array[mid] === target){
            ans = mid
            end = mid -1 ;
        }else if(array[mid]>target){
            end = mid-1;
        }else{
            start = mid+1
        }
    }
    return ans;
}

const upper = (array, target, start, end) => {
    let ans = -1;
    while(start<=end){
        mid = Math.floor((start+end)/2)
        if(array[mid] === target){
            ans = mid
            start = mid + 1;
        }else if(array[mid]>target){
            end = mid-1;
        }else{
            start = mid+1
        }
    }
    return ans;
}

const solution = (input) => {
    const N = parseInt(input[0]);
    const A = input[1].split(" ").map(e => parseInt(e));
    const M = parseInt(input[2]);
    const B = input[3].split(" ").map(e => parseInt(e));

    A.sort((a,b) => a-b)
    // console.log("A", A)

    let ans = ''
    B.forEach(
        (value,idx) => {
            const loweridx = lower(A, value, 0, N-1);
            // console.log("loweridx : ", loweridx)
            const upperidx = upper(A, value, 0, N-1);
            // console.log("upperidx : ", upperidx)

            let result = 0
            if (loweridx !== -1 && upperidx !== -1 ){
                result = upperidx-loweridx+1
            } else {
                result = 0
            }
            idx == M-1 ? ans += result : ans += `${result} `
        }
    )
    console.log(ans)

}

const input = [];
rl.on("line", function(line){
    input.push(line);
}).on("close", function(){
    solution(input);
    process.exit();
})

 

3. 문제 번호 1654

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

정말.... 정말 어려웠던 문제입니다 ㅠㅠ 정답 비율도 20%밖에 안되네요.

위에서 어떤 배열을 가지고 해당 배열 안에서 이진 탐색을 이용해 값을 찾던 것과 달리

이 문제는 전체 범위 안에서 mid값이 어떤 조건을 만족하는가?! 에 대하여 true/false를 확인 후에 범위를 변경하는 식으로 사용되었습니다.

(사실 이건 답을 찾아봤는데도 그 답을 이해하는 시간도 상당히 걸렸네요...ㅎㅎ)

const readline = require('readline')
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
})

function binarySearch (A, N, max) {
    let mid = 1
    let min = 1
    let ans = 1
    while(max>=min){
        let n = 0;
        mid = Math.floor((max+min)/2);

        A.forEach((value, idx) => {
            n += Math.floor(value/mid)
        })

        if(n<N){
            max = mid-1
        }else{
            ans = mid
            min = mid+1            
        }        
    }
    console.log(ans)
}

const solution = (input) => {
    const K = parseInt((input[0].split(" "))[0])
    const N = parseInt((input[0].split(" "))[1])
    let A = []
    for (let i=1;i<input.length;i++){
        A.push(parseInt(input[i]))
    }

    let max = 0
    for (i=0;i<A.length;i++){
        max += A[i]
    }
    max = Math.floor(max/N)

    binarySearch(A,N,max)


    // const result = binarySearch(A,N,max)
    // console.log(result)
}

const input = [];
rl.on("line", function(line){
    input.push(line);
}).on("close", function(){
    solution(input);
    process.exit();
})

 

위 코드는 봐도 헷갈린다는 것을 알기에 설명을 조금 덧붙여보겠습니다.

• 우선 랜선을 모두 더한 후 개수로 나눈 231이 max값이 됩니다.
• 가장 작게 자를 수 있는 단위가 1이므로 min값은 1로 잡아주었습니다.
• mid값을 구하여 해당 값으로 각 랜선을 잘랐을 때 나온 개수의 합(n)을 필요한 랜선의 개수 N과 비교해주었습니다.
• 이때 n이 N보다 작으면 랜선의 길이가 더 짧아야 한다는 의미이기 때문에 max를 mid-1로 이동합니다.
• n이 N 이상이면 해당 값을 일단 저장한 후 min위치를 mid+1로 이동합니다. (두 번째 문제 최대 인덱스를 구하는 이진 탐색법과 같은 방식입니다.)
• 이것을 max와 min값이 일치할 때까지 반복 후 최종 값을 return 합니다. (여기선 양식 없이 값 하나만 출력되어 바로 console로 찍었습니다.)