[알고리즘&코딩테스트] 이분 탐색 (Binary Search) 문제

목차

· 수열에서의 탐색이란?

· 이분 탐색이란?

- 이분 탐색의 시간 복잡도

- 이분 탐색에서 자주 하는 실수

- 이분 탐색 작동 방식

 

수열에서의 탐색이란?

· 수열과 탐색 대상 X가 주어졌을 때, 다음의 질문을 던지는 것

- X가 존재하는가?

- X [이하, 미만, 이상, 초과]의 원소는 몇 개가 있는가?

- X와 가장 가까운 원소는 무엇인가?

 

· 아래 그림 처럼 정렬 되지 않은 수열이 주어지면 탐색 속도는 O(N)이다.

X = 63

72

19

38

58

10

92

18

11

87

 

· 아래 그림 처럼 정렬된 수열이 주어지면 이분 탐색으로 더 빠르게 탐색할 수 있다.

10

11

18

19

38

58

72

87

92

 

이분 탐색이란?

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

- 시간 복잡도 O(log N)

X = 63

10

11

18

19

38

58

72

87

92

 

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

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

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

 

이분 탐색 작동 방식

· 위치를 나타내는 3개의 L, R, M을 사용하여 코드를 표현한다.

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

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

Result := 탐색한 X의 위치

M := (L+R) / 2

 

· 찾으려는 데이터와 M 위치(중간점)에 있는 데이터를 반복적으로 비교한다.

자세한 내용: https://scshim.tistory.com/369

 

X = 63

10

11

18

19

38

58

72

87

92

 

이분 탐색의 시간 복잡도

· 수열의 A[M]과 찾으려는 데이터 X를 한 번 비교할 때마다 [L, R] 구간이 절반씩 좁아진다.

- 즉 구간의 길이는 N -> N/2 -> N/4 -> ... -> 1의 순서로 점점 좁아진다.

- 즉, "총 비교 횟수"는 "구간의 변화 횟수"인 O(log N)만에 원하는 값을 탐색한다.

 

이분 탐색에서 자주 하는 실수

1. 입력된 배열을 정렬하지 않고 이분 탐색을 하는 경우

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

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

 

예제 문제 1

· BOJ 7795 - 먹을 것인가 먹힐 것인가  https://www.acmicpc.net/problem/7795

· 문제 파악

- N = 20,000, M = 20,000인 경우 가장 연산이 많다. N * M = 4억 => Integer 자료형 사용 가능

- A 각 원소에 대해 B의 모든 원소를 차례대로 비교하는 경우 O(N*M) => 최대 4억의 연산이 필요하므로 이는 시간 초과다.

- B 원소에 탐색 시간을 줄이기 위해 B를 정렬하고, 이분 탐색하자. 이 경우 O(NlogM)의 시간 복잡도가 발생한다.

- 시간 복잡도 O((N+M)logM)

1. B 배열 정렬 => O(MlogM)

2. 모든 A의 원소마다, B 배열에 대해 이분 탐색 => O(NlogM)

3. 총 시간 복잡도: O((N+M)logM)

 

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class N7795 {
   static Scanner sc = new Scanner(System.in);
   static int T;
   static int N, M;
   static int[] A, B;
   public static void main(String[] args) {
      T = sc.nextInt();
      for (int i = 0; i < T; i++) {
         input();
         pro();
      }

      sc.close();
   }

   private static void pro() {
      // B배열에 대해 이분탐색을 하기 위해 정렬한다.
      Arrays.sort(B);

      int ans = 0;
      for (int i = 1; i <= N; i++) {
         //A[i]를 선택하면, B에서는 A[i]보다 작은 게 몇 개나 있는 지 count하기
         ans += lowerBound(B, 1, M, A[i]);/* TODO */
      }
      System.out.println(ans);
   }

   /*
     * A[L...R]에서 X미만의 수 중 제일 오른쪽 인덱스를 Return 하는 함수
     * 일치하는 수가 없다면 L -1을 return
    */
   private static int lowerBound(int[] A, int L, int R, int X) {
      int result = L - 1;
      while(L <= R) {
         int mid = (L + R) /2;
         if (A[mid] < X) {
            L = mid + 1;
            result = mid;
         } else if (A[mid] >= X) {
            R = mid - 1;
         }
      }
      return result;
   }

   private static void input() {
      N = sc.nextInt();
      M = sc.nextInt();
      A = new int[N+1];
      B = new int[M+1];
      IntStream.range(1, N+1)
         .forEach(i -> A[i] = sc.nextInt());
      IntStream.range(1, M+1)
         .forEach(i -> B[i] = sc.nextInt());
   }
}

 

· 추천 문제: BOJ 1920 - 수 찾기 /  BOJ 1764 - 수 찾기 /  BOJ 3273 - 수 찾기 /  BOJ 10816 - 수 찾기

 

예제 문제 2

· BOJ 2470 - 두 용액  https://www.acmicpc.net/problem/2470

· 문제 파악

- 2 <= N <= 100,000 / -10억 <= 원소 <= 10억  -> Integer 가능

 

· 가장 쉬운 방법: 선택 가능한 두 용액을 전부 비교하기 O(N^2)

- 10^2 == 100억이므로 시간 초과

- 가장 쉬운 방법은 찾는 과정은 개선할 수 있는 부분을 찾을 수 있고, 부분 점수를 받을 수 있다는 점에서 유용하다.

 

· 빠른 방법: O(NlogN)

- A[left]라는 원소를 골랐다면 해당 원소에 '-'부호를 붙인 -A[left]와 값이 비슷할 수록 좋다.

- 즉, A[left]를 정했을 때, -A[left]와 가장 가까운 걸 찾자.

- 정렬의 장점:

1. 이분 탐색에 사용할 수 있다.

2. 가장 가까운 원소는를 빠르게 찾을 수 있다.

 

- 시간 복잡도: O(NlogN)

1. 배열 정렬 한 번 => O(NlogN)

2. 모든 원소마다 Left로 정하고, -A[Left]를 이분 탐색 => O(NlogN)

 

public class N2470_두용액 {
   static int N;
   static int[] A;

   public static void main(String args[]) {
      input();
      pro();
   }

   private static void input() {
      Scanner sc = new Scanner(System.in);
      N = sc.nextInt();
      A = new int[N];
   }

   private static void pro() {
      Arrays.sort(A); // 이분 탐색을 위한 정렬

      int bestSum = Integer.MAX_VALUE;
      int v1 = 0, v2 = 0;

      for(int left = 1; left <= N -1; left++) {
         // A[left] 용액을 쓴다. 즉, -A[left]와 가장 가까운 용액을 자신의 오른쪽 구간에서 찾자.
         int res = lowerBound(A, left+1, N, -A[left]);

         // A[res-1]와 A[res] 중에 A[left]와 섞었을 때의 정보를 정답에 갱신시킨다.
         if (left + 1 <= res -1 && res -1 <= N && Math.abs(A[res-1] + A[left]) < bestSum) {
            bestSum = Math.abs(A[left] + A[res -1]);
            v1 = A[left];
            v2 = A[res - 1];
         }
         if (left + 1 <= res && res <= N && Math.abs(A[res] + A[left]) < bestSum) {
            bestSum = Math.abs(A[left] + A[res]);
            v1 = A[left];
            v2 = A[res];
         }
      }
      StringBuilder sb = new StringBuilder();
      sb.append(v1).append(" ").append(v2);
      System.out.println(sb);
   }

   // A[L...R] 에서 X이상의 수 중 제일 왼쪽 인덱스를 return 하는 함수
   // 그런 게 없다면 R + 1을 return 한다.
   private static int lowerBound(int[] A, int L, int R, int X) {
      int res = R + 1;
      while(L <= R) {
         int mid = (L + R) / 2;
         if(A[mid] >= X) {
            res = mid;
            R = mid - 1;
         } else {
            L = mid + 1;
         }
      }
      return res;
   }
}