[알고리즘] 정렬된 데이터에서의 탐색, 이진 탐색

 

이진 탐색

 

이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾을 때 효율적인 알고리즘이다.

주요 특징은 대상 데이터의 중앙값과 탐색 대상 값을 비교하고, 데이터 크기를 절반씩 줄이면서 찾는다는 것이다.

 

정렬된 데이터가 있는 경우, 굉장히 유효하게 사용되는 일반적인 알고리즘이기에 꼭 숙지해야 한다.

 

 

이진 탐색의 과정

1. 현재 데이터 셋의 중앙 값을 찾는다.
2. 중앙 값 > 타깃 값인 경우, 중앙 값 기준 왼쪽 데이터 셋에서 다시 탐색한다.
3. 중앙 값 < 타깃 값인 경우, 중앙 값 기준 오른쪽 데이터 셋에서 다시 탐색한다.
4. 이 과정을 반복하다가 중앙 값 = 타깃 값이 된 순간 종료한다.

 

 

 

이진 탐색 문제 예시 1

 

백준 1920번 문제를 통해서 이진 탐색이 사용되는 간단한 예시를 알 수 있다.

1920번: 수 찾기

 

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] A = new int[n];
        for(int i=0; i<n; i++) {
            A[i] = sc.nextInt();
        }

        Arrays.sort(A);
        int m = sc.nextInt();

        for(int i=0; i<m; i++) {
            boolean find = false;
            int target = sc.nextInt();
            int start=0;
            int end = A.length - 1;
            while(start <= end) {
                int mid = (start+end)/2;
                int midV = A[mid];
                if (midV > target) {
                    end = mid - 1;
                } else if (midV < target) {
                    start = mid + 1;
                } else {
                    find = true;
                    break;
                }
            }
            if (find) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }



    }
}

 

이진 탐색 자체는 시간 복잡도가 O(logN)이다.

자바에서 제공되는 sort()는 nlogN만큼의 시간복잡도가 소요되므로, 따로 문제가 되진 않는다.

 

문제 자체는 이진 탐색의 개념만 숙지하면, 알 정도여서 크게 어렵지 않았다.

 

 

 

이진 탐색 문제 예시 2

 

2343번: 기타 레슨

 

백준 2343번 문제는 레슨 시간이 주어지고, 블루레이의 최소 크기를 찾는 문제이다.

이진 탐색에서는 이렇게 범위가 주어진 정답 영역에서 최소 답안을 찾는 방법이 되기도 한다.

 

 

import java.util.*;
import java.io.*;
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++) {
                if (sum + A[i] > middle) {
                    count++;
                    sum = 0;
                }
                sum += A[i];
            }

            if (sum != 0) {
                count++;
            }
            if (count > m) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        System.out.println(start);
     }

}

 

- 최소 값은 레슨 중에 제일 긴 레슨 시간이 되어야 한다.

- 최대 값은 레슨의 시간을 전부 합한 값이다.

- 블루레이를 사용한 개수를 체크하며, 이진 탐색을 통해 값의 범위를 줄여준다.

 

 

이진 탐색 문제 예시 3

1300번: K번째 수

 

이 문제는 이진 탐색을 사용하는 것 자체를 떠올리기가 힘들다.

또한 k보다 작은 값의 개수를 2차원 배열에서 찾아내는 규칙을 발견해야 한다.

 

 

 

import java.util.*;
import java.io.*;
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();

        int start = 1;
        int end = k;
        int ans = 0;

        while(start <= end) {
            int middle = (start + end) / 2;
            int cnt = 0;

            for(int i=1; i<=n; i++) {
                cnt += Math.min(middle / i, n);
            }
            if (cnt < k) {
                start = middle + 1;
            } else {
                end = middle - 1;
                ans = middle;
            }
        }

        System.out.println(ans);
    }

}

 

 

 

풀이 자체는 굉장히 간단하다. 그 만큼 그 규칙을 찾기 힘들다는 말이기도 하다.

중요한 것은 k보다 작은 수를 세는 아이디어 자체인 것이다.

 

 

- 한 행에서 중앙 값보다 작거나 같은 수를 찾아야 한다.

- 이 때, 각 행은 1의 배수 형태, 2의 배수 형태, 3의 배수 형태... 와 같이 이루어져 있다.

- 이러한 상황에서 중앙 값보다 작거나 같은 수를 찾기 위해서는, 중앙 값에서 각 행의 번호(1, 2, 3...)을 나누었을 때의 값과 각 행의 번호 그 자체에서 더 작은 값 하나를 선택한다.

- 중앙 값보다 작거나 같은 수의 갯수가 k보다 크거나 같은 경우에 정답을 저장한다.

 

 

 

Reference

- Do it! 코딩 테스트 - 기초 편