패스트캠퍼스 챌린지 25일차

이분 탐색 응용편

 

매개 변수 탐색 (Parametric Search)

  1. 정답을 매개변수(Parameter) 로 만들고 Yes/No 문제(결정문제) 로 바꾸기

  2. 모든 값에 대해서 Yes/No 를 채웠다고 생각했을 떄, 정렬된 상태인지 확인

  3. Yes/No 결정하는 문제를 풀기 

 => 문제를 거꾸로 푸는것이기 때문에 통찰력을 요구, 많은 훈련이 필요함

 

자주하는 실수

 1. 매개 변수에 대한 결정이 No/Yes 꼴이 아닌데 이분 탐색 하는 경우

 2. L, R, M Result 변수의 정의를 헷갈려 부등호 등을 잘못 쓰는 경우

 3. L,R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우! 

 

어떠한 경우에 매개변수 탐색을 쓰는것이 좋은가

<키워드>

 - ~의 최대값을 구하시오

 - ~의 최솟값을 구하시오

 

나무자르기 핵심 구현

 - 기존 문제 : 원하는 길이 M 만큼 얻을 수 있는 최대 높이는 얼마인가?

 - 뒤집은 문제 : 어떤 높이로 잘랐을떄, 원하는 길이의 M 만큼 얻을 수 있는가? (Yes/No)

   시간 복잡도 O(N)

  static boolean determination(int H) {
        // H 높이로 나무들을 잘랐을 때, M 만큼을 얻을 수 있으면 true, 없으면 false를 return하는 함수
        long sum = 0;
        for (int i = 1; i <= N; i++) {
            if (A[i] > H) {
                sum += A[i] - H;
            }
        }
        return sum >= M;
    }

    static void pro() {
        long L = 0, R = 2000000000, ans = 0;
        // [L ... R] 범위 안에 정답이 존재한다!
        // 이분 탐색과 determination 문제를 이용해서 answer를 빠르게 구하자!
        while (L <= R) {
            int mid = (int) ((L + R) / 2);
            if (determination(mid)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        System.out.println(ans);
    }

1. 높이(H) 를 정해서 결정 문제 한 번 풀기 => O(N)

2. 정답의 범위를 이분 탐색하면서  풀기 => O(log X) 번 반복

3. 총 시간 복잡도 : O(Nlog X)

 

 

공유기 설치 핵심 구현

기존 문제 : C개의 공유기를 설치했을 떄, 최대 인접거리(D)는 얼마인가?

뒤집은 문제 : 어떤 거리(D)만큼 거리를 둘 떄, 공유기 C개를 설치할 수 있는가? Yes/No

 

    static boolean determination(int D) {
        // D 만큼의 거리 차이를 둔다면 C 개 만큼의 공유기를 설치할 수 있는가?

        // 제일 왼쪽 집부터 가능한 많이 설치해보자!
        // D 만큼의 거리를 두면서 최대로 설치한 개수와 C 를 비교하자.
        int cnt = 1, last = A[1];
        for (int i = 2; i <= N; i++) {
            if (A[i] - last < D) continue;
            last = A[i];
            cnt++;
        }
        return cnt >= C;
    }

    static void pro() {
        // determination을 빠르게 하기 위해서 정렬해주자.
        Arrays.sort(A, 1, N + 1);

        int L = 1, R = 1000000000, ans = 0;
        // [L ... R] 범위 안에 정답이 존재한다!
        // 이분 탐색과 determination 문제를 이용해서 answer를 빠르게 구하자!
        while (L <= R) {
            int mid = (L + R) / 2;
            if (determination(mid)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        System.out.println(ans);
    }

 

시간,공간복잡도 계산

1. 주어진 집들 정렬 => O(NlogN)

2. D를 정해서 결정 문제 한 번 풀기 => O(N)

3. 정답의 범위를 이분 탐색하면서 풀기 => O(logX) 번 반복

4. 총 시간 복잡도 : O(NlogN + NlogX)

 

 

 

25일차 인증

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]