이분탐색 OBOE 피하기

이정빈·2024년 5월 9일

알고리즘

목록 보기

1/15

이분탐색 문제 풀이 시 겪은 문제

알고리즘 문제 중 이분탐색 문제를 풀다보면 항상 헷갈리는 부분이 있다. 이분탐색의 원리는 알겠는데 while문의 조건을 left<right로 할지 left<=right로 할지도 헷갈리고 정답을 left로 할지 left+1로 할지, right로 할지 right-1로 할지 굉장히 헷갈린다.

이렇게 +1이나 -1 때문에 발생하는 오류를 OBOE : Off by One Error라고 한다.

자꾸 알고리즘 문제에서 이 오류로 인해 틀려서 정리를 하려고 한다.

간단한 예시로 살펴보기

이분탐색(Binary Search)은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법이다. 이때 결정 문제란 답이 Yes or No인 문제를 의미한다.

예를 들어 배열에서 5 >= num 인 가장 큰 num을 찾으라고 한다고 가정하고, 주어진 배열은 1, 5, 3, 6, 2, 7, 8 이라고 하자.

먼저 이분탐색을 하려면 정렬을 해야한다. 따라서 배열을 정렬하면 1, 2, 3, 5, 6, 7, 8 이 될 것이다. 이제 5 >= num을 찾아야하는데 이 조건을 boolean check() 메소드라고 하면 1, 2, 3, 5는 True를 6, 7, 8은 False를 반환할 것이다. 따라서 T,T,T,T,F,F,F인 배열이 될 것이다.

이제 여기서 우리는 어떤 것을 찾아야하는지 보자. 5 >= num인 가장 큰 값이 조건이므로 True 중 가장 큰 값을 출력해야한다.

그럼 이제 코드로 작성해 보자.

먼저 left와 right 변수를 설정해야한다. 이 때 check(left) != check(right) 이어야한다. 그 이유는 T와 F가 연속적으로 있을 때 T와 F의 경계를 찾아야하기 때문에 두개가 달라야지 left <= 정답 <= right가 보장된다.
다음으로 while 조건을 left +1 < right 로 입력한다. 그 이유는 while문이 끝났을 때 left와 right가 바로 옆에 붙어있게 하기 위함이다. 이렇게 함으로써 left는 True의 가장 큰 값을 right는 False의 가장 작은 값을 가리킨다.
이제 while문 안에서 문제에서 주어진 조건에 따라서 left = mid나 right = mid를 입력한다. 예시라면 아래처럼 코드를 짠다.

        int [] arr = {1, 2, 3, 5, 6, 7, 8};
        int left = 0; //첫번째 인덱스
        int right = 7; // 인덱스를 사용하므로 arr[7]은 존재하지 않아 무조건 false이다.
        int mid = 0;
        while(left+1 <right){
            mid = (right + left) / 2;
            if( 5>= arr[mid]) left = mid; // 만족하는 경우
            else right = mid; //만족하지 않는 경우
        }

        System.out.println(arr[left]);

정답에서 요구하는 것에 따라 left나 right를 입력한다. 여기 예시에서는 True중 가장 큰 값이므로 left가 답이 된다.

실제 문제로 살펴보기

실제 문제를 살펴보자.

백준 1654번 랜선자르기

위 문제에서는 첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력해야한다.

그렇다면 check 함수를 어떻게 생각해야할까?
check 함수를 몇 미터로 잘라야지 랜선 N개를 만들 수 있을까? 로 정의할 수 있다.

이제 left와 right에 대해 생각해보자.

`left`

0미터로 자르는 것은 논리적으로 불가능하다. 따라서 최소 값이 1미터이고, 1미터로 자른다면 True일 것이다. 따라서 left는 1로 잡고, check(1) = True임을 알 수 있다.

`right`

right에 대해 생각해보면 주어진 나무 길이 중 가장 큰 값 max에 대해 생각해보자(입력 받을 때 max를 구했다고 가정). check(max)는 무조건False이지는 않다. 예를 들어 K == N인 경우 max미터로 잘라도 된다. 하지만 max + 1은 최대 길이보다 크게 자르는 것이라서 논리적으로 불가능 하고 check(max+1) = False이다. 따라서 right는 max +1로 설정한다.

그러면 아래와 같이 코드를 짤 수 있다.

public class 나무_자르기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long N = Long.parseLong(st.nextToken());
        long M = Long.parseLong(st.nextToken());

        long [] arr = new long[(int) N];

        st = new StringTokenizer(br.readLine());
        long max = 0;
        for(int i=0; i<N; i++){
            long num = Long.parseLong(st.nextToken());
            arr[i] = num;
            if(max < num) max = num;
        }

        // 이분탐색
        long left = 0;
        long right = max;
        long mid;
        while(left+1<right){
            mid = (left + right) /2;

            long count = 0;
            for(int i=0; i<N; i++){
                if(arr[i] > mid){
                    count = count + arr[i] - mid;
                }
            }
            // 절단 가능
            if(count >= M){
                left = mid;
            }

            //절단 실패
            else {
                right = mid;
            }
        }

        bw.write(left+"");
        bw.flush();


    }
}