[개념 학습 및 정리] 이진 탐색, Parametric Search

1. 이진 탐색

1) 이진 탐색이란 ?

일반적으로 n개의 숫자 중 특정 숫자를 찾을 경우 모든 원소를 확인하기 때문에 시간 복잡도는 O(n)이 된다. 이진 탐색은 정렬되어 있는 숫자들 중에서 특정 숫자를 찾는 방법이기에 O(n)의 시간복잡도보다 더 빠르다.

 

• 정렬되어 있는 수 중 중간 값을 찾음
• 중간 값이 찾고자 하는 값보다 클 경우 오른쪽, 작을 경우 왼쪽
• 과정 반복

 

이진 탐색

2) 시간 복잡도

이진 탐색은 숫자를 절반씩 지워나가면서 찾기 때문에 n을 몇번을 2로 나누어야 1이 되는지가 시간복잡도이다. 즉, O(log n)이다. 하지만 결국 정렬을 해야하기 때문에 O(n logn)이다. 그럼에도 효율적으로 사용되는 상황은 다음과 같다.

• 이미 배열이 정렬되어 있을 경우
• 숫자 찾기가 많을 경우

3) 이진 탐색 재귀 디자인

• int binarySearch(int[] arr, int s, int e, int value)는 s번째 부터 e번째 값 중 value를 찾는 함수 못찾는다면 -1 반환
• if(s > e) return -1; 주어진 값이 없을 경우 동작 확인
• else if(s == e) { if(value == arr[s]) return true; else return false; } 주어진 값이 하나 일 경우 동작 확인

 

재귀 호출 방식은 다음과 같다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st_1 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st_1.nextToken()); // 배열 수
        int k = Integer.parseInt(st_1.nextToken()); // 찾고자 하는 수

        StringTokenizer st_2 = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(st_2.nextToken());

        Arrays.sort(arr);
        // 값을 찾을 경우 찾은 위치 반환, 못찾은 경우 -1 반환
        bw.write(binarySearch(arr, 0, n-1, k) + "");

        bw.flush();
        bw.close();
        br.close();
    }

    static int binarySearch(int[] arr, int s, int e, int value) {
        if(s > e) return -1; // 주어진 수들이 없을 때
        else if(s == e) { // 주어진 수들이 하나 일 때
            if(arr[s] == value) return s;
            else return -1;
        } else {
            int mid = (s + e) / 2;
            if (arr[mid] < value) return binarySearch(arr, mid+1, e, value);
            else if (arr[mid] > value) return binarySearch(arr, s, mid - 1, value);
            else return mid;
        }
    }
}

비재귀적 호출 방식은 다음과 같다. 단, 시작과 끝은 어떤 값을 가르키는지 정확하게 정의해야한다. 시작은 찾고자 하는 값보다 항상 작은 값을 가르키며 끝은 찾고자 하는 값보다 항상 큰 값을 가르킨다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st_1 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st_1.nextToken()); // 배열 수
        int k = Integer.parseInt(st_1.nextToken()); // 찾고자 하는 수

        StringTokenizer st_2 = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(st_2.nextToken());

        Arrays.sort(arr);
        // 값을 찾을 경우 찾은 위치 반환, 못찾은 경우 -1 반환
        bw.write(binarySearch(arr, 0, n-1, k) + "");

        bw.flush();
        bw.close();
        br.close();
    }

    static int binarySearch(int[] arr, int s, int e, int value) {
        if(arr[s] > value || arr[e] < value) return -1;

        int start = s;
        int end = e;
        int mid = 0;
        while(start+1 < end) {
            mid = (start + end) / 2;

            if(arr[mid] > value) end = mid;
            else if(arr[mid] < value) start = mid;
            else return mid;
        }
        return -1;
    }
}

 

 

 

2. Parametric Search

1) Parametric Search

매개변수 탐색은 이진 탐색을 이용하여 문제를 해결하는 테크닉이다. N개(1이상 100000이하)의 숫자와 S가 주어질 때 몇 개의 연속된 값을 합해야 그 합이 S이상이 되는지에 대한 문제가 대표적이다. 이 문제의 해결 방법은 답(구간 설정)을 정해두고 그 답이 맞는지 확인하면 된다.  처음부터 끝까지 모두 다 해보기에는 시간이 오래 걸리기 때문에 구간은 가능한 구간과 가능하지 못한 구간의 경계를 찾고, 찾은 패턴을 이용하여 문제에 접근하면 된다.

※ 여기서 구간은 몇 개의 연속된 값인지를 뜻한다. 예를 들어 구간이 3이라면, 3 개의 연속된 값을 뜻한다.

2) 시간 복잡도

처음부터 끝까지 모두 다 해보는 방식대로라면, 시도를 해보아야 하는 구간의 개수는 최악의 경우 O(n)의 시간이 걸리기에 O(n^2)의 시간이 걸리게 된다. 하지만 이진 탐색을 통해 가능한 구간과 가능하지 못하는 구간의 경계를 찾게 된다면, 더 빨라진다.

 

• 특정 구간이 가능한지 판단하는데 걸리는 시간은 O(n)
• 시도를 해보아야 하는 구간의 개수는 O(log n)
• 즉, O(n log n)

3) Parametric Search 재귀 디자인

시작점은 반드시 가능하지 못해야 하며, 끝점은 반드시 가능해야 한다.

package org.example;

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

public class Test {

    private static int n = 0;
    private static int s = 0;
    private static int[] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st_1 = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st_1.nextToken());
        s = Integer.parseInt(st_1.nextToken());

        arr = new int[n];
        StringTokenizer st_2 = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st_2.nextToken());
        }

        // 시작점은 1, 끝점은 제일 큰 값 n
        // 시작점은 무조건 x를 가르키며, 끝점은 o를 가르킨다.
        int start = 0;
        int end = n;

        // 첫번째 구간이 가능할 경우
        if(check(1)) {
            bw.write(1 + "");
            return;
        }
        // 마지막 구간이 불가능 할 경우
        if(!check(n)) {
            bw.write(-1 + "");
            return;
        }

        // 이진 탐색
        while(start+1 < end) {
            int mid = (start+end)/2;

            if(check(mid)) end = mid;
            else start = mid;
        }

        bw.write(end + "");
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean check(int interval) {
        // 구간의 길이 interval만큼 정했을 때, 그 합이 s이상인 경우를 판단
        int sum = 0;
        for(int i = 0; i < interval; i++) sum += arr[i];
        if(sum >= s) return true;

        for(int i = 0; i < n-interval; i++) {
            sum = sum - arr[i] + arr[i+interval];
            if(sum >= s) return true;
        }
        return false;
    }

}