(25.04.05) 이분탐색의 활용

알고리즘을 보다보면, 정말 간단한 이분탐색의 활용도, 문제의 기준점을 어떻게 잡냐에 따라서 생각하는데 한참 걸리기도 한다.

특히 이번 문제일 경우에도, 

 

공유기를 멀리 떨어뜨려야 한다 -> 이분탐색을 사용한다 -> 집 순서를 left right mid로 잡아서 를 멀리 떨어 뜨려야한다. -> 그런데 집 거리가 주어진다 -> left right 을 사용하는데 조건이 있다

 

이런 고민이 있어 한참을 생각했던 문제이다.

하지만, 템플릿을 활용하는데에 있지, 집간 거리 자체를 기준점으로 잡는다면 오히려 접근하는데 굉장히 쉬워진다.

---

 

집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

public class Main {

    public static void main(String args[]) throws Exception {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputArr = reader.readLine().split(" ");

        int n = Integer.parseInt(inputArr[0]);
        int c = Integer.parseInt(inputArr[1]);

        int[] houses = new int[n];
        for (int i = 0; i < n; i++) {
            houses[i] = Integer.parseInt(reader.readLine());
        }

        Arrays.sort(houses);

        // 거리를 이분법으로 시행
        // 최소거리, 최대거리 정하기
        int left = 1;
        int right = houses[n-1] - houses[0];

        // 정답
        int answer = 0;

        while(left <= right) {
            int mid = left + (right - left)/2;

            // 마지막 설치 위치 ~ mid 위치 보다 큰 거리 일때만 router 갯수를 카운트
            // 첫번째는 설치

            int routerCount = 1;

            int lastRouter = houses[0];
            for (int i = 1; i < n; i++) {
                if((houses[i] - lastRouter) >= mid) {
                    routerCount++;
                    lastRouter = houses[i];
                }
            }

            // 설치 공유기가 c 이상으로 많아 버리면 left를 중간값으로 갱신
            // 그렇지 않을 경우 right 을 중간값으로 갱신
            if(routerCount >= c) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }

        System.out.println(answer);
    }
}

• 기본적인 이분법 템플릿을 따라간다면 쉽게 구현할 수 있는 알고리즘이지만 “무엇을” 이분탐색으로 조절하면서 부분탐색해야하는지가 중요함
• 위 데이터는 두가지 다른 Parameter를 가지고 있는데 , 집의 순서 / 집의 거리 이렇게 두가지가 있음

 // 가장기본적인 이분탐색 플로우
 public static int binarySearch(int[] arr, int target) {
        int left = 0; // 계속 중간 mid가 정해져야하기 때문에 0이더라도 무시하지 않고 지정해줘야함
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 자동 캐스팅으로 내림

            if (arr[mid] == target) {
                return mid; // 값을 찾은 경우 인덱스 반환
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반으로 이동
            } else {
                right = mid - 1; // 왼쪽 절반으로 이동
            }
        }

        return -1; // 값을 찾지 못한 경우 -1 반환
    }

• 기본 템플릿으로 접근하게 된다면, 집의 순서(인덱스) 를 기준으로 할 수 있지만, 또 다른 집의 거리 라는 Parameter가 주어진다면 이를 적극적으로 활용할 수 있음
• Greedy 알고리즘 접근법 적용 : 처음과 끝 집간 거리의 중간부터 탐색을 잡는 것이기 때문에 첫 집으로부터 두번째 집을 최대한 가능한 멀리 잡아야함
  • 그리고, 공유기의 갯수가 맞아야함

주의

• 반드시 Target에 도달하는 순서를 잡는 것이아니라, 조건에 따라서 다른 값(위에서는 거리) 부분탐색을 진행할 수 있음
  • left 와 right 이 집의 순서 index 일 필요가 없음
• 반환하는 최대/최소 값이기 때문에 공유기를 다 설치를 해도, ( routerCount = c 이어도) 계속 부분탐색을 진행해서 가장 적절한 mid 값을 찾는 것임을 주의
  • routerCount를 반환하는 것이 목적이 아니기 때문에 c만큼 공유기를 설치해도 이상적인 값이 나오지 않을 수 있음

---

이분탐색이라 쉽다고 넘길 수 있지만, 충분히 한번더 살펴봐야할 필요가 있다고 생각했기에 기록하고,
그리고 이분탐색 외에도 너무 내 나름대로 정리했던 템플릿에 너무 고수할 필요가 없다고 생각했다.