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

이분 탐색(Binary Search)

 - 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 이분하면서 탐색하는 방법

 

오름차순이 정렬이된 배열의 특성

- 임의의 M번 인덱스에 있는 배열 A의 A[M]이 기준 X 보다 크다면 A[M...N]은 전부 x 보다 크다.

- 임의의 M번 인덱스에 있는 배열 A의 A[M]이 기준 X 보다 작다면 A[1...M]은 전부 x 보다 작다.

 

 

 L : 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스

 R : 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스

 Result : 탐색한 X의 위치

 탐색 목표 : X이하의 원소 중에 가장 오른쪽에 있는 원소

 

자주하는 실수

  1. 입력된 배열에 바로 이분탐색을 하는데, 정렬을 하지 않는 경우

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

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

 

 

먹을것인가 먹힐것인가 (백준 7795)

1. 문제 파악

   - 정답의 최대치를 파악하라 (N = 20000, M = 20000)

     => N * M => 4억 1초 미만 (Integer 사용)

 

구현

 static int lower_bound(int[] A, int L, int R, int X) {
        // A[L...R] 에서 X 미만의 수 중 제일 오른쪽 인덱스를 return 하는 함수
        // 그런 게 없다면 L - 1 을 return 한다

        int res = L - 1;  // 만약 A[L...R] 중 X 이하의 수가 없다면 L - 1 을 return 한다.
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] < X) {
                res = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return res;
    }

    static void pro() {
        // B 배열에 대해 이분탐색을 할 예정이니까, 정렬을 해주자!
        Arrays.sort(B, 1, M + 1);
        
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            // A[i] 를 선택했을 때, B 에서는 A[i]보다 작은 게 몇 개나 있는 지 count하기
            ans += lower_bound(B, 1, M, A[i]);
        }
        System.out.println(ans);
    }

 

두 용액

- 서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만들어라

 

구현

 static int lower_bound(int[] A, int L, int R, int X) {
        // A[L...R] 에서 X 이상의 수 중 제일 왼쪽 인덱스를 return 하는 함수
        // 그런 게 없다면 R + 1 을 return 한다

        int res = R + 1;  // 만약 A[L...R] 중
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] >= X) {
                res = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return res;
    }

    static void pro() {
        // A 에 대해 이분 탐색을 할 예정이니까, 정렬을 미리 해주자.
        Arrays.sort(A, 1, N + 1);

        int best_sum = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;
        for (int left = 1; left <= N - 1; left++) {
            // A[left] 용액을 쓸 것이다. 고로 -A[left] 와 가장 가까운 용액을 자신의 오른쪽 구간에서 찾자.
            int candidate = lower_bound(A, left + 1, N, -A[left]);

            // A[candidate - 1] 와 A[candidate] 중에 A[left] 와 섞었을 때의 정보를 정답에 갱신시킨다.

            // 1. A[left] + A[candidate - 1]
            if (left < candidate - 1 && Math.abs(A[left] + A[candidate - 1]) < best_sum) {
                best_sum = Math.abs(A[left] + A[candidate - 1]);
                v1 = A[left];
                v2 = A[candidate - 1];
            }

            // 2. A[left] + A[candidate]
            if (candidate <= N && Math.abs(A[left] + A[candidate]) < best_sum) {
                best_sum = Math.abs(A[left] + A[candidate]);
                v1 = A[left];
                v2 = A[candidate];
            }
            
        }
        sb.append(v1).append(' ').append(v2);
        System.out.println(sb);
    }

 

 

 

 

24일차 인증

 

 

 

 

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

https://bit.ly/37BpXiC

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