이진탐색

오늘은 이진 탐색에 대해 정리해보려 한다.

영어로는 Binary Search라고 한다.

이진 탐색은 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는다.

-값들 중에 절반을 기준으로 원하는 값을 찾는다.

-절반을 나눈 값을 기준으로 원하는 값이 있는 쪽에서 다시 절반을 나눈다.

즉 이진 탐색은 숫자를 절반씩 지워나가면서 찾는다.

따라서 시간 복잡도는 O(log n)이 된다.

 

여기서 의문점이 들 수 있다.

정렬해야 하면 O(log n)이 아니라 결국 O(n log n) 아닌가요? -> yes

따라서 이미 배열이 정렬되어 있다면 Binary Search가 효율적이다.

또는 숫자 찾기를 엄청 많이 해야 하는 경우에는 오히려 정렬을 한 뒤에 Binary Search를 하는 것이 좋다.

 

 

 

이제 이진 탐색을 구현해보자.

 

1. 재귀 함수를 사용하여 구현

import java.util.Scanner;

public class Main{
    static int n;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n =sc.nextInt();
        int q =sc.nextInt();
        arr = new int[n];
        for (int i=0;i<arr.length;i++){
            arr[i] = sc.nextInt();
        }
        Check(0,n-1,q);

    }
    //반으로 쪼개어 탐색
    static void Check(int start , int end, int s){
        if (start>end){
            System.out.println(-1);
            return;
        }
        if (arr[start]==s){
            System.out.println(start);
            return;
        } else if (arr[end]==s) {
            System.out.println(end);
            return;
        }
        int mid = (start+end)/2;
        if (arr[mid]==s) {
            System.out.println(mid);
            return;
        }
        if (arr[mid]<s){
            Check(mid+1,end,s);
        }
        else {
            Check(start,mid-1,s);
        }

    }


}

중요한 점은 재귀 함수 부분에서 시작 부분과 끝부분이 우리가 찾는 값이면 바로 그 위치를 반환하는 것이다.

만약 우리가 찾는 값이 없으면 -1을 반환하게 구현하였다.

 

 

 

2. 비재 귀적 구현

 

import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n =sc.nextInt();
        int q =sc.nextInt();
        arr = new int[n];
        for (int i=0;i<arr.length;i++){
            arr[i] = sc.nextInt();
        }
        Check(0,n-1,q);
    }
    //반으로 쪼개어 탐색
    static void Check(int myStart , int myEnd, int s){
        int start,end,mid;
        if (arr[myStart]>s){
            System.out.println(-1);
            return;
        } else if (arr[myStart]==s) {
            System.out.println(myStart);
            return;
        }
        if (arr[myEnd]<s){
            System.out.println(-1);
            return;
        } else if (arr[myEnd]==s) {
            System.out.println(myEnd);
            return;
        }
        start =myStart;
        end =myEnd;
        while (start+1<end){
            mid = (start+end)/2;
            if (arr[mid] ==s){
                System.out.println(mid);
                return;
            } else if (arr[mid]>s) end = mid;
            else start=mid;
        }
        System.out.println(-1);
    }
}

재귀로 구현한 것을 단순하게 비 재귀로 표현한 것이라 동작원리는 같다.

 

 

 

 

 

이제 이진 탐색 알고리즘을 어디에 사용할 수 있는지 궁금할 것이다. 

 

 

  숫자 개수 세기

이 문제에서 이진 탐색을 사용하는 이유는 간단하다.

숫자 찾기를 엄청 많이 해야 하는 경우에는 오히려 정렬을 한 뒤에 Binary Search를 하는 것이 좋기 때문이다.

 

정답 코드

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

//숫자 세기
public class Main {
    static int n;
    static int[] arr;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n =sc.nextInt();
        int q = sc.nextInt();
        arr = new int[n];
        for (int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        for (int i=0;i<q;i++){
            int request = sc.nextInt();
            int front = frontFind(request);
            int end = endFind(request);
            if (front==-1) System.out.println(0);
            else System.out.println(end-front+1);
        }
    }
    static int frontFind(int result){
        int start;
        int end;
        if (arr[0] <result) start=0;
        else {
            if (arr[0]>result)return -1;
            else return 0;
        }
        if (arr[n-1]>=result)end=n-1;
        else return -1;
        while (start+1<end){
            int mid=(start+end)/2;
            if (arr[mid]<result)start = mid;
            else end = mid;
        }
        if (arr[end]==result)return end;
        else return -1;

    }

    static int endFind(int result){
        int start;
        int end;
        if (arr[0]<=result)start=0;
        else return -1;
        if (arr[n-1]>result)end=n-1;
        else {
            if (arr[n-1]<result)return -1;
            else return n-1;
        }
        while (start+1<end){
            int mid=(start+end)/2;
            if (arr[mid]<=result)start=mid;
            else end =mid;
        }
        if (arr[start]==result)return start;
        else return -1;
    }
}

 

 

이진 탐색을 사용하기 위해 수를 정렬한다.

이후 frontFind, endFind매서드를 만들어서 처음 값이 등장한 index와 마지막에 등장하는 index를 구한다.

그 차이를 구하면 된다. 이진 탐색을 이용하면 시간 복잡도에서 엄청난 이점을 가져갈 수 있다.

 

 

 

나무 자르기

위 문제도 이진 탐색을 사용하여 효율적으로 풀 수 있다.

이유는 간단하다. 만약 5층까지 있다고 하자.

3층으로 나누었을 때, 가능하다면 4,5층은 시도하지 않아도 가능하다는 것을 알 수 있다. 

 

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int M = in.nextInt();

        int[] tree = new int[N];

        int start = 0;
        int end = 0;

        for(int i = 0; i < N; i++) {
            tree[i] = in.nextInt();
            if(end < tree[i]) {
                end = tree[i];
            }
        }

        // 이분 탐색 
        while(start < end) {

            int mid = (start + end) / 2;
            long sum = 0;
            for(int treeHeight : tree) {

                if(treeHeight - mid > 0) {
                    sum += (treeHeight - mid);
                }
            }
            if(sum < M) {
                end = mid;
            }
            else {
                start = mid + 1;
            }
        }

        System.out.println(start - 1);

    }
}

알고리즘을 살펴보면, 나무들 중에 최댓값을 구한다. -> 자를 수 있는 최대의 높이

이진 탐색을 이용하여 중간 값을 기준으로 가능 여부를 확인한다.

나무의 잘린 길이 = 나무의 높이 - 자르는 위치

잘린 나무의 길이의 합을 구하고 그 값이 우리가 원하는 값과 비교한다.

더 크다면, 높이를 높여도 된다. 개수가 부족하다면 높이를 낮추어 더 많은 나무를 잘라야 한다.

 

 

NN단표

특정 숫자가 몇 번째인가?

이 문제 또한 이진 탐색을 활용하여 풀 수 있다.

정답 코드

import java.util.Scanner;

// NN 단표
public class Main {
    static long n;
    static long k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        k = sc.nextLong();
        long start = 1,end=n*n+1;
        while (start+1<end){
            long mid = (start+end)/2;
            long myOrder = getOrder(mid);

            if (myOrder<=k)start=mid;
            else end =mid;
        }
        System.out.println(start);
    }
    static long getOrder(long x){
        long result=0;
        for (int i=1;i<=n;i++){
            if (i*n<x)result+=n; //맨 마지막수
            else {
                if (x % i == 0) result += (x / i) - 1;
                else result += x / i;
            }
        }
        return result+1;
    }
}

이진 탐색을 사용한 부분은 우리가 찾는 수가 시작점에 위치할 때까지 반으로 나누게 된다.

즉 해당수보다 작은 값의 개수를 찾는 것이 관건이다.

따라서 getOrder매서드가 중요해진다.

n이 4면 아래와 같다.

1 2 3 4

2 4 6 8

3 6 9 12

4 8 12 16

앞의 수만 보면 x보다 작은 수를 구할 수 있다.

만약 x가 12라 하면 앞에 1 2 3 4는 모두 작기 때문에 총 개수 4개를 더한다.

근데 만약 4번째 줄처럼 12가 포함될 경우 카운트를 하면 안 된다.

따라서 12가 4로 나누어지면 -1을 해준다.

또한 중요한 점은 수의 범위가 매우 커지기 때문에 long타입으로 설정해야 한다.

 

 

중복 없는 구간

이 문제도 이진 탐색을 사용한다.

처음 이진 탐색을 어떻게 사용할지 의문이 들었는데, r을 찾을 때 이진 탐색을 사용한다.

예를 들어 4번째 줄보다 크다면 1,2,3은 당연하게도 연속되지 않는 수열이 있다.

 

정답 코드

import java.util.Scanner;

public class Main {
    static int n;
    static int[] arr;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        for (int i=0;i<arr.length;i++){
            arr[i] = sc.nextInt();
        }
        int start = 1;
        int end = n;
        if (!checkLength(start)){
            System.out.println(1);
            return;
        }
        if (checkLength(end)){
            System.out.println(end);
            return;
        }
        while (start+1<end){
            int mid = (start+end)/2;
            if (checkLength(mid))start=mid;
            else end=mid;
        }
        System.out.println(start);
    }

    static boolean checkLength(int length){
        int index = 0;
        int[] count = new int[n+1];
        int overlap =0;
        for (int i = index; i<index+length;i++){
            count[arr[i]]++;
        }
        for (int i=1;i<=n;i++){
            if (count[i]>=2)overlap++;
        }
        if (overlap==0)return true;
        while (index+length<n){
            count[arr[index]]--;
            if (count[arr[index]]==1)overlap--;
            index++;
            count[arr[index+length-1]]++;
            if (count[arr[index+length-1]]==2)overlap++;
            if (overlap==0)return true;
        }
        return false;

    }
}

동작 과정을 보면, 길이 1과 n을 검사하여 중복인 구간이 있는지 없는지를 본다.

1은 중복구간이 될 수가 없기 때문에 start를 1로 설정한다.

n을 검사할 때 중복이 없다면 제일 긴 길이기 때문에 n을 반환한다.

중복인 구간이 없다면 더 큰 구간을 봐서 최댓값을 구해야 한다. 중복인 구간이 있다면 더 작은 값을 확인해야 한다.

중요한 부분은 중복인 구간을 검사할 때 시간을 줄이는 것이다.

count는 해당 숫자가 얼마나 나왔는지 알려준다.

count배열의 값들이 모두 1 이하이면 중복이 없다는 것을 의미한다.