모각코PS / 백준 2110 공유기 설치

모각코 PS스터디

지난주 알고리즘 스터디 내용 중 대표적인 한 문제를 정리해보려고 합니다. 늘 그렇듯 문제는 알고리즘 대장님께서 선정해주셨습니다.😃

문제와 풀이

---

문제 링크 : 백준 2110번 - 공유기 설치

👇펼쳐서 코드와 해설 읽기

진짜 할 말이 많은데... 일단 넋두리 & 이분탐색 tip은 마무리로 넘겨두고... 로직의 흐름 부터 보시죠.

로직의 흐름은 이렇습니다.

표본 수가 매우 큽니다. 대강 눈으로만 봐도 판단 횟수가 10억 * 20만이니까, 그리디로는 택도 없습니다. logN의 시간 복잡도로, 대강 열댓번 정도의 탐색으로 끝내야할 것 같습니다. 이를 위해 이분탐색으로 풀 것입니다. 정확히는 파라메트릭 서치를 적용할 거에요.

지금 궁금한 건 거리죠. 최소 거리와 최대 거리를 탐색 범위로 두면 됩니다. 그러면 탐색하다가 적절한 거리를 찾으면 프로그램이 끝나겠죠? 코드에서는 최소 거리를 l로 두고, 최대 거리를 r로 두겠습니다.

당장 수행할 주요 목표는 이렇습니다. : 설치가 가능하면서도 가장 큰 거리 찾기 & 설치불가능한 케이스는 빠르게 패스.
이 목표를 달성하기 위해서는 아래와 같은 계획이 필요합니다.

현재 목표 거리(x)에서 목표 개수(c)만큼 설치가 가능한지.
가능하다면 -> 목표 거리를 1씩 늘려보기. (l = x + 1)
불가능하다면 -> 목표거리를 이분하기(근데 그 이분 지점이 x니까, r에 x를 대입(r = x)하기)

l과 r이 만나는 지점은 최초로 설치가 불가능해진 거리입니다. 좀 더 풀어서 설명해볼게요.
가능해진 위치를 찾으면, 하한(l)을 1늘림으로써 '간격(x)을 1씩 늘려가면서' '불가능해질 때까지' 탐색을 반복하기로 했습니다. 불가능해지면 탐색은 끝이에요.
그렇단 말은, 불가능해진 해당 위치에서 1을 빼면, 가능했던 최대의 간격 x를 구할 수 있다는 말이겠지요? <= 요 문장을 "A"라고 하겠습니다.
그래서, 설치가 가능한 케이스일때는 l을 1씩을려서 간격을 늘리고, 불가능한 케이스는 빠르게 제외하기 위해서 이분하며(r = x) 탐색을 진행하다가,
불가능한 케이스 중 가장 작은 숫자를 담고 있는 r과, 밑에서부터 1씩 증가해 올라오던 l이 만나면! "A" 상황이 되는 것이겠죠!
그러면 그 때 l - 1해주면~ 우리가 찾던 x를 구해지는 거라는 말이 되겠어요.

말이 좀 복잡한데, 이해가 안될 수도 있을 것 같아요. 대충 그런가보다 하고 코드를 훑어보시고, 마무리로 넘어가주세요.
똑같은 고민을 하면서 저 나름대로 정리해본 내용을 남겨두겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Nick {

    public static void main(String[] args) throws IOException {
        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());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        Arrays.sort(arr);

        int l = 1; // 최소로 가질 수 있는 거리
        int r = arr[arr.length - 1] - arr[0]; //최대로 가질 수 있는 거리
        /*
            위 l/r을 기준으로, 가질 수 있는 거리를 이분탐색한다. (탐색위치는 대충 x라 하자)
            좀 더 구체적으로 말해서, 지금 하고 싶은 건, 설치가 가능하면서도 가장 큰 거리 찾기 & 불가능한건 가능한 빠르게 제끼기.
            위의 요구사항을 감안해서 실행 계획을 짜보자.
            탐색위치에서 c개만큼 설치가 가능한지,
                가능하다면 -> l = 가능했던 위치 + 1; //가능한 위치를 하나씩 올릴거야, 불가능할 때까지 / '불가능해지는 위치 - 1' = '가능한 최대 간격')
                불가능하다면 -> r = 불가능했던 위치; //불가능했던 위치는 더 고려할 필요가 없다 && l이 r(불가능해지는 위치)까지 올라오는 시점을 체크할 용도
        */
        while (l <= r) {
            int x = ((r - l) / 2) + l;

            if (canInstall(arr, x, c)) { // 설치가 가능한지 : 가능
                l = x + 1;
            }
            else { // 설치가 불가능
                if (r <= x) break; // 무한루프 케이스
                r = x;
            }
        }

        System.out.println(l - 1); // (불가능해지는 간격 - 1) => 가능한 최대 간격
    }

    private static boolean canInstall(int[] arr, int x, int c) {
        int count = 1; //처음 한 개는 무조건 설치
        int installed = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (installed + x <= arr[i]) {
                installed = arr[i];
                count++;
            }
            if (count == c) return true;
        }
        return false;
    }

}

마무리

---

이분탐색(파라메트릭 서치) 개념을 처음 접하게 된 문제였습니다. 그래서 뭔 소린지 도통 모르겠더라구요. 진짜 너무 고생했어요.

이분탐색의 개념 자체는 너무 쉽죠. 절반 나눠서, 해당 안되는 부분은 빠르게 잘라낸다. 해당되는 부분은 또 절반 나눠서 검사한다. 해를 찾을 때까지 반복한다.
너무 쉬워요. 근데 그래서 더 좌절감이 들었던 거 같아요.
무슨 말인지 알겠는데, 적용하려면 하나도 모르겠는거.
이분탐색 개념은 알았는데, 문제는 뭔 소린지 하나도 모르겠는거.
더 화가 나는 건, 설명하는 블로그 포스팅을 찾아 봐도, 한글인데도 무슨 말인지 모르겠다는 거!!! ('최소값 중 최대값을 구해라'라는 말이 도대체 무슨 의미인가요... 설명하시는 분만 알아들으시면 어떻게 해요... 솔직히 지금 봐도 뭔 말인지 모르겠..)

그래서 이분탐색 개념을 설명하기 보다는, 이분탐색 문제를 만났을 때 반드시 우선적으로 고려할 점을 정리해보았습니다.
저도 계속 알듯말듯한 상태로 헤매다가, 이렇게 정리해놓고나서 문제를 접하다보니까 패턴이 보이기 시작하고 문제에 손을 댈 수 있게 되더라구요.

이분탐색(파라메트릭서치)를 접할 때 고려할 점 2가지

1. 찾고 있는 것이 무엇인가? : 현재문제를 예로 들면, '간격'을 찾고 있죠. => 이걸 달리 말하면, 탐색의 기준이 될 것이 바로 '간격'이라는 거에요. 그렇다면 우리는 이분탐색을 진행하려고 하니, 이 '간격'의 최소 간격과 최대 간격을 구해놓고 양가값(l, r)으로 사용해야 합니다.
2. 상한선을 찾고 있는지, 하한선을 찾고 있는지? : 문제는 뭔가를 찾는데, 찾는 것에 '조건'을 붙여놓습니다. 이 조건을 만족하면서 어떤 값을 찾고 있는지에 관심을 둬야합니다.
   1. 문제가 "[조건을 만족하면서] **가능한 넓은**"과 같은 표현을 쓴다면(현재 문제의 표현으로는 '[설치가 가능한 인접 공유기] 중 (가장 간격이 넓은)') 상한선을 찾고 있는 것입니다. 그때는 지금 문제의 코드처럼, 가능할 때에 탐색값을 1씩 늘리다가 불가능해질 때의 값을 캐치해서 -1 해주면 되겠죠?
   2. 문제가 "[조건을 만족하는] **최소값**"과 같은 표현을 쓴다면 하한선을 찾고 있는 것입니다. 상한선을 구할 때와 반대의 로직으로(탐색값을 1씩 좁히는 방향으로) 탐색값을 찾으면 되겠죠?
   3. 문제가 "[조건을 만족하는] **범위**의 크기"와 같은 표현을 쓴다면, 상한선 - 하한선을 구해야 합니다(물론 +1도 적절히 해주어야겠죠). 가능한 케이스의 하한과 가능한 케이스의 상한을 별도로 구해서, 두 값의 차를 구하면 조건을 만족하는 범위를 알 수 있겠죠.

이 정도만 계속 염두하시면서 문제를 접하면, 이분탐색은 풀 수 있다고 생각이 듭니다.
풀기 전에는 진짜 엄두도 안나게 어렵고 뭔 소린지 모르겠는데, 풀고 나니까 '이걸로 고생했다고?'라는 생각이 드는 케이스 중에서 '이분탐색' 카테고리가 최고였던 것 같아요.
물론 더 어려운 문제로 나아가면 노답일 수 있겠지만...😂 그건 그때가서 문제니까요. ㅎㅎ

일주일 전, 아니 단 며칠 전만 해도 이분탐색이 뭔지도 몰랐는데, 스터디 때문에 빠르게 습득한 것 같아요.

결론: 알고리즘 스터디 짱짱👍 해결할 때까지 앉아있는다고 10시간 스트레이트로 앉아있었던 내 궁뎅이 수고했다...