이분탐색은 탐색기법중 하나로, 원하는 탐색범위를 두 부분으로 분할해서 원하는 값을 찾는 방식이다.

이분탐색

이분탐색은 탐색기법중 하나로, 원하는 탐색범위를 두 부분으로 분할해서 원하는 값을 찾는 방식이다. 그렇기 때문에 전부를 탐색하는 경우 O(n)에 비해 이분탐색은 O(logn)의 시간으로 단축시킬 수 있다.

이분탐색을 이용한 binary search는 이전 장에서 설명했으므로, 이번장에선 활용문제를 풀어보도록 하자.

이전 장 링크 : 이진탐색(binary search)과 이분탐색(parametric search)_(1)

랜선 자르기

문제 링크 : 백준1654 랜선자르기

랜선자르기1 랜선자르기2

요약 : 주어진 k개의 랜선으로 n개의 랜선을 만들고 싶다. 이떄 만둘 수 있는 최대 랜선의 길이를 구해라.

풀이 : 가능한 랜선의 길이 0부터 2^31-1까지 정렬 되어있다고 하자. 우리는 0부터 2^31-1로 정렬된 배열에서 이분탐색을 이용해 최종길이를 찾을 수 있다. 가능한 길이 중 최대길이를 구하는 문제이므로 앞에 이진탐색의 upper_bound로 풀 수 있다.

이진탐색하는 과정을 좀더 자세하게 알아보자. 랜선 길이의 최대값이 1000이라고 하면 아래 그림과 같이 중간값을 decision()에 대입해 가능한 답이 되는지 확인 한다. 가능하다고 판단되면 즉, true가 나오면 중간값보다 더 큰 값도 가능한지 탐색한다. 반대로 false가 나오면 랜선의 길이가 더 작아야 한다는 의미이므로 탐색범위를 왼쪽 절반으로 줄인다.

랜선자르기3

위의 탐색과정을 하는 함수 optimize()를 구현해 준다.

//랜선 n개를 만들 수 있는 최대 길이 반환
static long optimize(){
        long lo = 0;
        long hi = Integer.MAX_VALUE;
        hi++;
        while(lo<hi){
            long mid = (lo+hi)/2;
            if(decision(mid)) lo = mid + 1;//가능하면 더 긴것도 해보기
            else hi = mid;  //불가능하면 더 짧은거 해보기
        }
        return lo-1;
    }

❓ 자주 찾는 질문 ❓

  • hi++;를 하는 이유
    ➜ 가능한 랜선의 길이는 0~2^31-1까지다. Integer.MAX_VALUE는 2^31-1인데 mid를 구하는 과정에서 나누기2를 하면 2^31-1이 절대 답이 될 수 없게 된다. (lo는 hi보다 항상 작기 때문에) 따라서 2^31-1이 답이 될 경우를 생각해 hi++;를 해주고 시작한다.

    • 그럼 hi = Integer.MAX_VALUE + 1; 하면 안되나요?
      ➜ 연산자 우선순위에 의해 (산술연산자가 대입연산자 보다 우위) Integer.MAX_VALUE+1가 먼저 계산되는데, Integer.MAX_VALUE+1은 오버플로우가 되어 Integer.MIN_VALUE와 같게된다.

  • int가 아닌 long을 사용하는 이유
    ➜ 위에서 hi++를 하면 int형 범위를 넘어버리기 때문에 long으로 선언해야 한다.

  • return lo-1;인 이유
    ➜ 앞장에서 구현한 upper_bound에선 그냥 lo를 반환하였다. 찾는 값의 다음 인덱스를 반환했기 때문이다. 하지만 여기서는 찾는 값의 인덱스를 반환해야 하므로 lo-1을 반환해준다.

전체코드 :

import java.io.*;
import java.util.StringTokenizer;

public class 랜선자르기 {
    static int k;
    static int n;
    static long len[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        len = new long[k];
        for(int i=0;i<k;i++){
            len[i] = Integer.parseInt(br.readLine());
        }
        System.out.println(optimize());
    }
    //mid길이로 n개의 랜선을 만들 수 있는지 반환
    static boolean decision(long mid){
        int count = 0;
        for(int i=0;i<k;i++){
            count += len[i]/mid;
        }
        return n <= count;
    }
    //랜선 n개를 만들 수 있는 최대 길이 반환
    static long optimize(){
        long lo = 0;
        long hi = Integer.MAX_VALUE;
        hi++;
        while(lo<hi){
            long mid = (lo+hi)/2;
            if(decision(mid)) lo = mid + 1;//가능하면 더 긴것도 가능한지 해보기
            else hi=mid;//불가능하면 더 짧은거 해보기
        }
        return lo-1;
    }
}