드디어! Binary Search 조건문 처리 헷갈림 해결 (+Lower Bound, Upper Bound)

LeeKyoungChang·2023년 8월 30일
새롭게 알게 된 알고리즘
0

새롭게 알게 된 알고리즘

목록 보기
1/1
post-thumbnail

저는 이분 탐색하다 조건문 처리에서 low <= high, low < high, low + 1 < high 중 어떤걸 선택해야할지,
결과가 low, high, (low + high)/2 인지 헷갈리는 점을 해결하기 위해 이 글을 작성하게 되었습니다.

 

목차
🤔 이 글을 왜 적었을까? 무슨 상황이야?
📖 이분 탐색이란
🧽 이분 탐색 구현
🛠️ lower_bound, upper_bound

 

🤔 이 글을 왜 적었을까? 무슨 상황이야?

🙋🏻 현재 나의 상황

이분 탐색 문제에서 특정 값을 찾는 문제 같은 경우는 쉽게 풀었지만, 근삿값을 구하는 문제에서(백준 예산, 과자 나눠주기)

while(조건문) 조건문 처리에서

  • left < right
  • left <= right

둘 중 어떤 걸 사용해야할지 감을 잡지 못해
이와 같이 (밑 사진와 같이)

이분 탐색 문제에서 계속 틀리고 있다 😭

특히, 코딩 테스트에서 최근들어 자주 접했지만 매번 틀리는 안타까움에 해결하기 위해 이분 탐색을 제대로 정리해보자 라는 생각에 작성하게 되었다.

 

시작하기에 앞서 제가 이해한 내용을 간단하게 소스로 설명하면 이와 같습니다.

ex) 특정 범위내에서 조건에 만족하는 최소값을 찾아야 하는 경우

public class Main {  
  
    private static int N, M;  // 
    private static int[] 배열;  
    private static boolean Check(int mid){  
        cnt 변수 선언

		ex)
		for(배열 길이){
			cnt에는 배열[인덱스] / mid의 결과를 합으로 더해준다.
		}

		와 같이 cnt에 결과값 저장
        
        cnt가 현재 찾는 값보다 크거나 같다면 true를 return 한다.
    }
      
    public static void main(String[] args){  
        int max = Integer.MAX_VALUE;
        binarySearch(0, max);
    }
      
    public static int binarySearch(int low, int high) {
        while (만약 low + 1이 high 보다 작은 경우) {
		    mid는 low와 high의 사이 중간 값이다.
			    Check함수에서는 mid(중간 값)을 활용해 조건에 해당한다면
				    - 조건에 해당한다면 low = mid
				Check함수를 통해 확인한 결과 조건에 해당하지 않는다면
					- 조건에 해당하지 않을 시 high = mid
		}

		현재 문제에서 최댓값을 구하라고 한다면 low을 return
		현재 문제에서 최솟값을 구하라고 한다면 high을 return
    }

 

 

📖 이분 탐색이란?

주어진 자료에서 중복되지 않은 값이 주어졌을 때 그 데이터 내에 특정 값이 존재하는지 검색하는 방법
보통, 1개의 결과값을 가지는 문제일 때 많이 사용된다.

즉, 결정 문제의 답이 이분적일 때 사용할 수 있는 탐색 기법이다.

 

✔️ 결정 문제란?

결정 문제 : Yes 또는 No인 문제를 의미하며 보통 1개의 매개변수를 가진다.

F, F, F ~ , T, T, T ~, T일 때 처음으로 v[i] >= val인 지점이 True가 되는 i 값이 결과값이다.

결정 문제의 매개변수(i, 안에서는 mid)에 대해 결정 문제의 답이 두 구간으로 나뉘는 것을 이분적이다 라고 하며 이런 경우 이분 탐색을 사용해 결정 문제의 답이 달라지는 경계를 찾을 수 있다.

 

이분 탐색은 경계를 포함하는 [low, high] 를 잡은 뒤 구간의 길이를 절반씩 줄여나가면서 low, high이 경계 지점에 위치하도록 하는 것이다.

이분 탐색이 끝난 뒤에는 low + 1 == high이며, Check(low) != Check(high)이다.
이때, Check(x)가 답이다.

  • Check(x) : 결정 문제에서 파라미터가 x일 때, 결정 문제의 답을 의미

이분 탐색은 구간의 범위가 클 때 효과적이라서 많이 사용된다.
또한, 최적화 문제에서도 사용되는데, 어떤 조건(Check(x))을 만족하는 x의 최댓값 또는 최솟값을 찾는 문제에서도 많이 사용된다.

  • 시간복잡도 : O(log n)

 

요약하면

(1) low, high의 반복문


low, high : 초기 값을 생각한다.

while(low + 1 < high)
	mid = (low + high) / 2;
 - if(Check(mid)) low = mid;
 - else high = mid;

return 최댓값인경우 low, 최솟값인경우 high

 

(2) Check 함수


Check(int mid)
long sum = 0;

for 배열 크기 만큼 반복문을 돌린다.
 - 특정 조건이라면 sum에 더해준다.

return sum >= 찾는 값

 

 

🧽 이분 탐색 구현

while(low + 1 < high)
 - [low, mid] or [mid, high]으로 줄여나간다.
 - Check(mid)가 low일 경우
	 - low 는 mid
 - Check(mid)가 high일 경우
	 - high는 mid

현재 low + 1 < high 이기 때문에, low와 high 사이에는 무조건 한 개 이상의 칸이 있다.
low + 1 == high 가 되는 순간 반복문은 종료가 된다.

종료될 때,

  • 가장 큰 F라면 low
  • 가장 작은 T라면 high

를 반환(정답으로 출력)해주면 된다.
(개인적인 생각으로 정답을 만족하는 최댓값을 구해라는 경우 low, 최솟값을 구해라는 경우 high을 정답으로 반환해주면 될 것 같다.)

 

(1) Low, High을 통해 Mid 값을 구한다.

스크린샷 2023-08-21 오후 10 09 39

 

(2) Check 함수를 통해 확인해본 결과 Check(Low) == Mid 라는 결과를 얻게 되었다.

스크린샷 2023-08-21 오후 10 09 44
  • 이때, Check(Low) == Mid 이므로, Low = Mid 가 된다.

 

(3) Check 함수를 통해 확인해본 결과 Check(Low) != Mid 라는 결과를 얻게 되었다.

스크린샷 2023-08-21 오후 10 09 48
  • 이때, Check(Low) != Mid 이므로, High = Mid가 된다.

 

(4) Low + 1 == High 가 되었기에 탈출한다.

스크린샷 2023-08-21 오후 10 09 53
  • Low, High는 경계에 위치한다.

 

 

✔️ 나무 자르기 문제

결정 문제로 mid 높이에 절단기를 위치했을 때 m 이상의 나무를 얻을 수 있는가? 로 주면 된다.
Low의 초기 값은 0, High의 초기 값은 가장 큰 나무의 높이로 설정하면 된다.

  • 임의의 mid 높이의 절단기로 각 나무를 모두 잘랐을 때, 나무의 길이가 m 이상인지 확인해주면 된다.
package 나무_자르기;  
  
import java.io.*;  
import java.util.*;  
  
public class BJ2805 {  
  
    private static int N;  
    private static long M;  
    private static long[] arr;  
  
  
    private static boolean Check(int mid){  
        long sum = 0;  
  
        // mid 절단기  
        for(int i = 0; i < arr.length; i++){  
            if(arr[i] > mid) sum += arr[i] - mid;  
        }  
  
//        System.out.println("sum : " + sum);  
  
        return sum >= M;  
    }  
    private static long binarySearch(){  
        int low = 0;  
        int high = Integer.MAX_VALUE;  
  
        while(low + 1 < high){  
            int mid = (low + high) / 2;  
            if(Check(mid)) low = mid;  
            else high = mid;  
        }  
  
//        System.out.println("low : " + low + " high : " + high);  
        return low;  
    }  
  
    public static void main(String[] args) throws IOException{  
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());  
        N = Integer.parseInt(tokenizer.nextToken());  
        M = Long.parseLong(tokenizer.nextToken());  
  
        arr = new long[N];  
        tokenizer = new StringTokenizer(reader.readLine());  
        for(int i = 0; i < N; i++){  
            long input = Long.parseLong(tokenizer.nextToken());  
            arr[i] = input;  
        }  
        Arrays.sort(arr);  
  
        System.out.println(binarySearch());  
  
        reader.close();  
    }  
}

 

 

🛠️ Lower Bound, Upper Bound

Lower Bound와 Upper Bound는 정렬된 배열에서 특정 값 이상 또는 초과인 원소가 처음으로 등장하는 위치를 찾는 문제에서 사용된다.

 

✔️ Lower Bound

Lower Bound는 v[i-1] < k <= v[i] 인 i를 찾아주는 함수로, v[i] >= k 인 i의 최솟값을 반환한다.

v의 모든 원소가 k보다 작다면 v의 마지막 다음 칸의 위치를 반환한다.

 

✔️ Upper Bound

Upper Bound는 v[i-1] <= k < v[i] 인 i를 찾아주는 함수로, v[i] > k 인 i의 최솟값을 반환한다.

v의 모든 원소가 k보다 작거나 같다면 v의 마지막 다음 칸의 위치를 반환한다.

 

스크린샷 2023-08-18 오후 11 43 06스크린샷 2023-08-18 오후 11 43 15

 

 

구현

✏️ Upper Bound와 Lower Bound는 이와 같은 규칙이 있다.

Upper Bound(v, v + n, x) - Lower Bound(v, v + n, x) == v 배열 내에서 성립하는 x의 개수

Upper Bound(v, v + n, x) : 배열 해당 구간 내에 원소 x에 해당하는 인덱스를 반환한다. (v[i] >= 3인 경우 => i)

v 배열이 오름차순으로 정렬되어 있을 때

  • v 내에 x가 없다면 0
  • v 내에 x가 있다면 idx1[x의 처음 등장 위치] - idx2[x의 마지막 등장 위치 + 1] 이 것은 v 배열 내에서 성립하는 x의 개수이다.

 

public class BinarySearch {  
    private static int lowerBound(int[] arr, int x){  
        int n = arr.length;  
  
        int low = -1; // high은 최소 0까지 감소할 수 있기 때문에, -1로 설정
        int high = n; // 모든 원소가 x보다 작은 경우 n을 반환해야 한다.
  
        while(low + 1 < high){  
            int mid = (low + high) / 2;  
            if(!(arr[mid] >= x)) low = mid;  
            else high = mid;  
        }  
        return high;  
    }  
  
    private static int upperBound(int[] arr, int x){  
        int n = arr.length;  
  
        int low = -1;  
        int high = n;  
  
        while(low + 1 < high){  
            int mid = (low + high) / 2;  
            if(!(arr[mid] > x)) low = mid;  
            else high = mid;  
        }  
        return high;  
    }  
  
    public static void main(String[] args) {  
        int[] arr = {1, 2, 3, 3, 4};  
  
        System.out.println(lowerBound(arr, 3)); // 2  
        System.out.println(upperBound(arr, 3)); // 4  
        System.out.println(upperBound(arr, 3) - lowerBound(arr, 3)); // 2  
  
    }  
}
  • Lower Bound는 주어진 값보다 같거나 큰 값이 처음으로 나오는 것을 찾는다.
  • Upper Bound는 주어진 값보다 큰 값이 처음으로 나오는 것을 찾는다.
  • 초기 값 설정
    • 가장 작은 값은 -1로 준다.
    • 가장 큰 값이면 결과로 주어진 배열 크기 값을 줘야 한다. 즉, 배열.length로 high 초기값을 지정한다.

 

 

🤨 그래서, 언제 써야 하는건데요?

범위가 큰 곳에서 특정 값을 찾을 때 사용한다.

밑의 내용은 개인적인 생각입니다.

 

✔️ 범위가 큰 곳에서 조건을 만족하는 특정 값을 찾을 때는

Binary Search 3개의 if문을 활용해 구현

 

✔ 최적화 문제, 어떤 조건(Check(x))을 만족하는 x의 최댓값 또는 최솟값을 찾는 문제

Check 함수를 활용해 구현한다.

  • Check 함수 반환 값이 true이면 low = mid
  • Check 함수 반환 값이 false이면 high = mid

 

✔️ 정렬된 배열에서 특정 값 이상 또는 초과인 원소가 등장 하는 처음 위치를 찾을 때

Lower Bound와 Upper Bound를 활용해 구현한다.

추가로, Lower Bound, Upper Bound에서도 Check 함수를 활용할 수 있을 것 같다.

 

구글링을 통해 학습하며 개인적인 생각으로 정리했습니다.
설명이 잘못된 게 있다면, 댓글로 알려주시면 감사하겠습니다!

 

 

profile
LeeKyoungChang
"야, (오류 만났어?) 너두 (해결) 할 수 있어"

0개의 댓글