Sorting and Searching -(3) 이분 탐색

⬛ 탐색 = 검색 = Searching

• ‘탐색’ 은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘

1) DFS : 깊이 우선 탐색

2) BFS : 너비 우선 탐색

3) Binary Seach : 이진 탐색(=이분 탐색)

---

Binary Seach : 이진 탐색(=이분 탐색, 이진 검색)

• 데이터가 정렬된 상태에서 대상 데이터 중앙값 vs 찾는 키 값 비교하여‘결정 알고리즘’도 이분 검색을 기반으로 한다.**[과정] : 탐색 대상 데이터가 오름차순 정렬됐다고 가정**2) 중앙값 < 찾는 키값 : 오른쪽 영역에 대한 탐색4) 1-3 반복하다가 (중앙값 == 찾는 키값) 일 때 탐색 종료
• 3) 중앙값 > 찾는 키값 : 왼쪽 영역에 대한 탐색
• 1) 중앙값 선택
• 시간 복잡도 O(log2n) : 검색 범위 매번 1/2 분할하여 비교하는 연산.
• 검색 범위를 절반씩 줄이는 알고리즘

---

6-8. 이분 검색(탐색) = Binary Search

import java.util.Arrays;
import java.util.Scanner;

/* 6-8. 이분 검색
[입력]
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
[출력]
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.*/
public class Main1 {
    //솔루션 함수 
    public int solution(int n, int m, int[]arr) {
        int answer= 0;
        //1)오름차순 정렬시켜놓고
        Arrays.sort(arr);

        int lt = 0, rt = n-1; //0인덱스부터 시작했으니 끝은 n-1

        while(lt<=rt) {
            int mid = (lt+rt) / 2;
            //중앙값 = m 이면 정답
            if(arr[mid] == m) {
                answer = mid+1;
                break;//답 찾았으니 탈출 

            }
            // 중앙값 > m : 왼쪽에서 탐색해야 함 
            if(arr[mid] > m) {
                rt = mid - 1;
            }
            // 중앙값 < m : 오른쪽에서 탐색해야 함 
            else {
                lt = mid+1;
            }
        } 

        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int m = kb.nextInt();

        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i] = kb.nextInt();

        System.out.println(T.solution(n, m, arr));
    }

}

---

결정 알고리즘 ← 이분 탐색의 응용

• 이분 탐색을 사용하여 답이 될 수 있는 값이 포함될 범위를 좁혀서 효율을 높이는 방식

6-9. 뮤직비디오 | 결정 알고리즘 

/* 6-9. 뮤직비디오 | 결정 알고리즘 
[입력]
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.
다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.
부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.
[출력]
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.
*/

import java.util.*;
class Main2 {
    //주어진 DVD 1개당 '용량'으로 전체 arr 용량을 몇개의 DVD에 담아내는지 확인  
    public int count(int[] arr, int capacity){
        int cnt=1, sum=0;
        for(int x : arr){
            //각 DVD 뽑아서 sum에 누적시킨 값이 용량 이상일 경우
            //다음 DVD로 카운팅 해야 함
            if(sum+x>capacity){
                cnt++;//다음 DVD에 담도록 
                sum=x;//새롭게 담길 현재 곡의 용량 x로 다시 세팅
            }
            else sum+=x;//용량아직 안벗어났으면 계속 누
        }
        return cnt;
    }

    public int solution(int n, int m, int[] arr){
        int answer=0;
        int lt=Arrays.stream(arr).max().getAsInt();
        int rt=Arrays.stream(arr).sum();
        //이분 검색하여 범위 좁히자
        while(lt<=rt){
            //이분 검색하여 범위 좁히자
            int mid=(lt+rt)/2;
            //2) 비교 후, 왼쪽 범위에서 다시 찾아봄 
            if(count(arr, mid)<=m){
                answer=mid; //우선 답 세팅
                rt=mid-1;//더 좁혀나가볼 것
            }//3) 비교 후, 오른쪽 범위에서 다시 찾아봄 
            else lt=mid+1;
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++) arr[i]=kb.nextInt();
        System.out.println(T.solution(n, m, arr));
    }
}

---

6-10. 마구간 정하기 (결정 알고리즘)

import java.util.*;

/* 6-10. 마구간 정하기 (결정 알고리즘) 
[입력]
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
[출력]
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
*/
public class Main3 {
    //유효 여부 
    public int count(int[]arr, int dist) {
        int cnt=1;
        int ep =arr[0];
        for(int i=1; i<arr.length; i++) {
            if(arr[i]-ep >= dist) {
                cnt++;
                ep=arr[i];
            }
        }
        return cnt;
    }

    //솔루션 함수
    public int solution(int n, int c, int[]arr ) {
        int answer= 0;

        //정렬
        Arrays.sort(arr);
        int lt = 1;
        int rt = arr[n-1];

        while(lt<=rt) {
            int mid = (lt+rt)/2;
            if(count(arr, mid) >= c) {
                answer=mid;
                lt = mid+1;
            }else rt = mid-1;
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int c = kb.nextInt();

        int[] arr = new int[n];

        for(int i=0; i<n; i++) arr[i] = kb.nextInt();        

        System.out.println(T.solution(n, c, arr));
    }
}