백준_공유기설치_이분탐색_2110

오늘은 이분탐색 문제를 풀이하려 한다. 

이 문제는 백준 단계별로 풀어보기에서 이분탐색 카테고리에 있는 골드 5문제이다. 문제를 읽는 순간 이게 무슨말이지? 하는 내용으로 생각이 되어 문제를 이해하는데만 오랜 시간이 걸렸다. 기본적으로 이분탐색 알고리즘을 푸는 순서를 한 번 정리하고자 한다. 

이분탐색이란 어떠한 대상을 두 부분으로 쪼개면서 탐색하는 방법론이다. 분할 정복은 어떤 전체문제를 해결하기 위해 부분적으로 나눠들어가면서 부분 문제를 해결하는 방식이라면, 이분탐색은 위 메커니즘과 유사하게 두 부분으로 나누어 들어가긴 하지만, 특정 값 또는 구간을 찾는 탐색이라는 것이다.

이분 탐색의 가장 쉬운 예시로는 UP&Down 게임이 있다. 기본적으로 업다운 게임을 진행할 때 무조건 전체 범위에 대해서 중간값만 부르면서 범위를 좁혀 나가지 않는가? 이런식으로 탐색 구간 내 절반을 잘라가면서 값을 찾아가는게 기본적인 이분 탐색의 원리이다. 

내가 찾고자 하는 데이터를 target이라고 하겠다. 

• 탐색 범위 내의 배열의 중간 인덱스를 구한다. 
• 중간 인덱스의 값과 target값을 비교한다. 
• target값이 중간값보다 작다면 왼쪽 부분을, target값이 중간 값보다 크다면 중간 값보다 오른쪽 부분을 탐색하고 같다면 해당 인덱스를 반환하고 종료한다. 

위의 과정을 반복하다보면 결과적으로 두 가지의 경우의 수로 수렴한다. target값을 찾은 경우 or target값이 탐색 대상에 없는 경우.

값을 찾은 경우는 찾은 값을 리턴한다. 

탐색 범위의 왼쪽 끝과(lo) 오른쪽 끝(hi)이 같은 경우까지 탐색하면 lo와 hi가 같아지는 순간이 오는데 이 값까지 찾고자 하는 target이 아니라면 탐색은 종료되고(lo와 hi가 교차되기 전까지 반복을 한다.) 이 말은 탐색 대상에 찾고자 하는 target값이 없다는 뜻이다. 

1. 이분탐색은 반드시 정렬된 상태로 진행해야 하기 때문에, 데이터를 배열에 담은 후 정렬한다. 
2. 탐색의 대상을 찾아야 한다. 어떤 값을 탐색의 범위로 잡아서 중간값을 찾아나갈 것인지를 정해야 한다.
3. 탐색의 대상을 찾았다면, 중간 값을 기준으로 탐색의 범위를 줄여나간다. 
   1. 이때 정확히 일치하는 값을 찾는지, 혹은 구간이 존재할 때 최대값(hi)을 찾는지, 구간의 최소값(lo)을 찾는지를 생각해보아야 한다. 
   2. 이에 따라 이분 탐색 과정에서 조건을 분기하는 방법이 달라지기 때문이다.

[이분탐색의 구조]

[기본] 정확히 일치하는 값을 구하고자 하는 경우 

int arr[] = new int[5];
int target = 5;
int lo = 0;                 //탐색 범위의 왼쪽   끝 인덱스
int hi = arr.length-1;        //탐색 범위의 오른쪽 끝 인덱스
        
//lo가 hi보다 커지기 전까지 반복한다. 
while(lo <= hi) {
    int mid = (lo+hi)/2;
    
    //target값이 중간 위치의 값보다 큰 경우 
    //중간값은 이미 비교로 사용했기 때문에 
    //다음의 탐색 범위는 mid를 제외한 하나 더 작은 수이다. 
    //ex) 1~100에서 업다운을 할 때, 50을 외쳐서 다운! 을 들었다면 
    //그 다음 탐색범위는 1~50이 아니라 1~49인 것과 같은 원리
    if(target > arr[mid]) {
        
        hi = mid-1;
    
    }
    else if(target<arr[mid]) {//작은 경우 
    
        lo = mid + 1; //위의 예시와 같은 원리이다. 
        
    }
    else {    //같은 경우 = target을 찾은 경우 
        
        //return mid; 중간값을 반환한다.
        
    }
    
    //return -1; 탐색에서 값을 찾지 못한 경우에는 음수를 반환한다.

 

 

[응용] 같은 값을 반환하는 구간의 시작점(하한)과 끝점(상한)을 구하는 경우

하한값이란 찾고자 하는 값 이상의★ 값이 처음으로 만나는 위치. 즉, 왼쪽부터 탐색을 하다가 찾고자 하는 값이 같거나 큰 경우를 처음 만나는 위치를 의미한다. -> 구간의 시작점!

//lo하한 -> 타겟이상의 값을 처음으로 만나는 인덱스 찾기
int arr[] = new int[5];
int target = 10;
 
int lo = 0; 
int hi = arr.length;
 
//lo가 hi랑 같아질 때까지 반복
while(lo < hi) {
    
    int mid = (lo + hi)/2;
    
    if(target <= arr[mid]) {
        hi = mid;
        
        //같을 수도 있기 때문에 기본 과정에서 처럼 mid-1이 아니라 mid로 상한을 내린다.  
    }else { //target > arr[mid]
        
        lo = mid+1;
        
        //하한값은 처음으로 타겟값 이상을 찾는 것이므로, mid+1로 하한을 올린다.
        
    }
    
    //return lo;
}

 

상한값이란 찾고자 하는 값을 초과한★ 값을 처음 만나는 위치이다.

//lo하한 -> 타겟이상의 값을 처음으로 만나는 인덱스 찾기
int arr[] = new int[5];
int target = 10;
 
int lo = 0; 
int hi = arr.length;
 
//hi상한 -> 처음으로 타겟을 초과하는 인덱스를 찾기
//lo가 hi랑 같아질 때까지 반복
while(lo < hi) {
    
    int mid = (lo + hi)/2;
    
    if(target < arr[mid]) {
        hi = mid;
        
        //타겟이 중간값보다 "작다"라는 내용이 보장된다. 
        //상한은 처음으로 초과하는 값이기 때문에 mid로 상한을 내린다. 
        
    }else { //target >= arr[mid]
        
        lo = mid+1;
        
        //상한은 타겟보다 항상 1크게(초과), 하한도 타겟보다 +1한 위치로 이동하기 때문에 
        //두 인덱스가 같아지는 경우는 상한 값을 찾은 경우이다. 
    }
    
    //return lo;
}

 

그렇다면 이제부터 본격적으로 문제를 접근해서 풀이해보자.

문제에서 요구하는 것을 기준으로 역으로 추적해보았다. 

문제에서는 공유기를 설치한 집 사이의 거리 중 최대값을 구하라고 했다. 이때, 무작정 공유기를 설치하는 것이 아니라 N개의 집에 C개의 공유기를 설치할 때, 인접한 공유기 사이의 거리의 최대를 구해야 한다.  참으로 무엇을 이분탐색의 대상으로 잡을지 고민하다가 공유기를 설치할 수 있는 거리의 최솟값(L)을 정해서 이 값을 기준으로 공유기를 설치했을 때, 설치할 수 있는 공유기의 수가 target값인 C보다 작다면 L을 줄이고, 크다면, L을 증가시키면서 설치할 수 있는 공유기의 수가 C가 되도록 이분탐색을 진행했다.

이때, 필자는 아무 생각없이 탐색을 진행했다가 오류를 범했는데, 그저 설치할 수 있는 공유기의 수가 C일때의 값을 return하도록 했더니 정확한 출력이 되질 않았다. 한참을 고민하다가 직접 그리면서 생각해보니 C개의 공유기를 설치하기 위한 두 집 사이의 최소 거리 L이 하나의 값이 아니었다. 결과적으로 말하면 이분탐색을 진행하되 위의 필자가 정리한 것처럼 기본으로 찾지 않고, "상한"값을 찾아야 한다는 것이다. 

그래야 문제의 조건에 맞도록 N개의 집에 C개의 공유기를 설치하는데, 인접한 공유기 사이의 거리를 최대(상한)로 만들수  있다.

아래의 소스코드에 달려있는 주석을 참고하면 이해하는데 큰 어려움은 없을 것이다.

package BinarySearch;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class _2110_공유기설치 {
    static int house[];
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        
        //집의 개수
        house = new int[N];
        
        for(int i=0; i< N; i++) {
            house[i] = Integer.parseInt(br.readLine()); //집의 좌표
        }
        
        Arrays.sort(house);
        
        //탐색해야 하는 범위는 두 집 사이의 거리이다. 두 집 사이의 거리로 가질 수 있는 최대최소값을 구한다.
        //인접한 두 집 사이의 거리로 가질 수 있는 최솟값
        int min=1;
        int max = house[N-1]-house[0]+1; //가장 멀리 있는 집부터 가장 앞에 있는 집 사이의 거리, 상한 값은 찾는 값보다 1크기 때문에 시작 범위도 1크게 잡아준다.
        
        while(min < max) {
        
            
            int mid = min+(max-min)/2; //오버플로우 방지
            
            if(install(mid)<C) {
                //중간에 있는 거리로 기준을 잡았을 때 설치할 수 있는 공유기의 수가 
                //문제에서 제시한 값보다 작다면. -> 거리를 줄여서 공유기를 더 설치 해야 한다. 
                //내가 찾는 거리는 중간 값보다 작다는 뜻이다.
                
                max = mid;
            }else {
                //중간에 있는 거리로 기준을 잡았을 때 설치할 수 있는 공유기의 수가
                //문제에서 제시한 값보다 크거나 같다면 -> 거리를 늘려서 공유기를 덜 설치해야 한다. 
                //내가 찾는 거리는 중간 값보다 크거나 같다는 뜻이다. 
                //이때 위의 조건 과는 달리 '같다'는 조건이 추가로 붙어있기 때문에 mid + 1로 이동해야 한다.
                min = mid + 1;
            }
            
            //상한 값은 탐색값을 초과하는 첫 번째 값을 가리키므로, -1을 해준다. 
             
        }
        System.out.println(min - 1);
        
    }
 
    private static int install(int mid) {
        // TODO Auto-generated method stub
        //mid값을 기준으로 설치할 수 있는 공유기의 수를 리턴한다. 
        //시작지점은 이미 공유기를 설치했다는 가정하에 카운트하고 시작 
        
        int count = 1; 
        
        //가장 마지막으로 설치한 위치  ->  시작 지점
        int last = house[0];
        
        for(int i=1; i<house.length; i++) {
            int current = house[i];
            
            if(current - last >= mid) {
                count++;
                last = current;
            }
        }
        
        
        return count;
    }
 
}

 

 

 

 

참고 : https://st-lab.tistory.com/m/261