이진 탐색 (Binary Search)

이진 탐색 (Binary Search)

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

기능	특징	시간 복잡도
타깃 데이터 탐색	중앙값 비교를 통한 대상 축소 방식	O(logN)

 

이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다. 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역이다.

 

핵심 이론

이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다. (내림차순이라면 조건 반대로)

 

이진 탐색 과정
1. 현재 데이터셋의 중앙값(median)을 선택한다.
2. 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

 

https://www.geeksforgeeks.org/binary-search-in-java/

 

위의 그림을 예로 들면, 정렬된 전체 10개의 데이터 중 23이란 값을 찾을 때 중앙값인 16과 비교한다. 16 < 23 이므로 오른쪽 데이터셋 (인덱스 5~9)을 선택한다. 다시 중앙값인 56과 비교하면 56 > 23 이므로 왼쪽 데이터셋을 선택한다. (인덱스 5~6) 중앙값을 보니 23, 23 == 23 이므로 값을 찾아 탐색을 종료한다.

 

---

 

[백준 1920번] 수 찾기

https://www.acmicpc.net/problem/1920

 

N의 최대 범위가 100,000이므로 단순 반복문으로는 이 문제를 풀 수 없다. 이진 탐색을 적용하면 O(nlogn) 시간 복잡도로 해결할 수 있으니 이진 탐색을 적용해 풀도록 하자. 이진 탐색은 정렬을 가정하므로 정렬 함수도 사용한다. 참고로 자바의 기본 정렬은 O(nlogn)의 시간 복잡도를 가지므로 정렬을 수행해도 제한 시간을 초과하지 않는다.

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            System.out.println(binary_search(Integer.parseInt(st.nextToken())));
        }
    }
    static int binary_search(int target) {
        int start = 0, end = arr.length - 1, mid = (start + end) / 2;
        while(start <= end) {
            if(arr[mid] == target) {
                return 1;
            }
            if (arr[mid] > target) {
                end = mid - 1;
            } else if(arr[mid] < target) {
                start = mid + 1;
            }
            mid = (start + end) / 2;
        }
        return 0;
    }
}

 

---

 

[백준 2343번] 기타 레슨

https://www.acmicpc.net/problem/2343

 

블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 선택하게 하는 실마리이다. 블루레이의 첫 레슨부터 마지막 레슨까지 차례대로 저장하다 보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다. 모두 저장할 수 있다면 블루레이의 크기를 줄이고 저장할 수 없다면 블루레이의 크기를 늘리는 방식으로 블루레이의 크기의 최솟값을 알 수 있다. 

 

이진 탐색 수행

이진 탐색의 시작 인덱스는 최대 길이의 레슨이고 종료 인덱스는 모든 레슨 길이의 합이다.

 

총 9개로 구성된 레슨의 시간은 각각 1, 2, 3, 4, 5, 6, 7, 8, 9이므로 이진 탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다. 블루레이 개수가 3일 때 9~45 사이에서 블루레이 크기의 최솟값을 이진 탐색으로 찾으면 된다. 

 

- 중앙값 크기로 모든 레슨을 저장할 수 있으면 종료 인덱스 = 중앙값 - 1

- 중앙값 크기로 모든 레슨을 저장할 수 없으면 시작 인덱스 = 중앙값 + 1

 

[정답]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] A = new int[n];
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            A[i] = sc.nextInt();
            if(start < A[i]) start = A[i];  // 레슨 최댓값을 시작 인덱스로 저장하기
            end += A[i];    // 모든 레슨의 총합을 종료 인덱스로 저장하기
        }
        while(start <= end) {
            int middle = (start + end) / 2;
            int sum = 0;
            int count = 0;
            for (int i = 0; i < n; i++) {   // middle 값으로 모든 레슨을 저장할 수 있는지 확인
                if(sum + A[i] > middle) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }
            if (sum != 0)   // 탐색 후 sum이 0이 아니면 블루레이가 1개 더 필요하므로 더함
                count++;
            if(count > m)
                start = middle + 1;
            else
                end = middle - 1;
        }
        System.out.println(start);
    }
}

 

---

 

[백준 1300번] K번째 수

https://www.acmicpc.net/problem/1300

 

k의 범위가 1~min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘은 사용할 수 없다. 여기서는 이진 탐색을 사용한다. 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B[k]값을 구한다. 다시 말해 작은 수의 개수가 k-1개인 중앙값이 정답이다. 작은 수의 개수를 세는 아이디어가 이 문제를 푸는 열쇠다. 

 

2차원 배열은 N행이 N의 배수로 구성되어 있으므로 2차원 배열에서의 k번째 수는 k를 넘지 않는다. 다시 말해 2차원 배열의 1~k번째 안에 정답이 있다. 이 점에 주목하여 이진 탐색의 시작 인덱스를 1, 종료 인덱스를 k로 정한다. 다음은 N=3, k=7일 때를 예로 든 것이다.

 

최초의 중앙값은 4이다. 중앙값보다 작거나 같은 수의 개수는 그림에서 알 수 있듯이 중앙값을 N으로 나눈 값이다. 단, 나눈 값이 N보다 크면 N으로 정한다. 1열은 1로 나눠 4, 2열은 2로 나눠 2, 3열은 3으로 나눠 1을 얻는다. 그 결과 각 열에서 중앙값 4보다 작거나 같은 수의 개수는 3, 2, 1로 6개가 된다. 중앙값보다 작거나 같은 수의 개수는 Math.min(middle / i, N)으로 계산한다. 그리고 이를 통해 중앙값 4는 6번째 수보다 큰 수가 될 수 없다는 것을 알 수 있으며, 중앙값 4보다 큰 범위에 정답이 있다는 것을 유추할 수 있다. 

 

정리하면 중앙값보다 작은 수의 개수가 k보다 작으면 시작 인덱스를 중앙값 + 1, 중앙값보다 작은 수의 개수가 k보다 크거나 같으면 종료 인덱스를 중앙값 - 1로 하면서 정답을 중앙값으로 업데이트하며 시작 인덱스가 종료 인덱스보다 커질 때까지 이진 탐색을 진행한다. 

 

자세한 설명은 이 블로그에 잘 되어 있으니 참고

 

https://st-lab.tistory.com/281

[백준] 1300번 : K번째 수 - JAVA [자바]

 

[정답]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long start = 1, end = K;
        long ans = 0;

        while(start <= end) {
            long middle = (start + end) / 2;
            long cnt = 0;
            // 중앙값보다 작은 수는 몇 개인지 계산하기
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(middle / i, N);
            }
            if(cnt < K)
                start = middle + 1;
            else {
                ans = middle;       // 현재 단계의 중앙값을 정답 변수에 저장하기
                end = middle - 1;
            }
        }
        System.out.println(ans);
    }
}

 

 

 

 

[참고 자료]

- 알고리즘 코딩 테스트 자바편