[Java] BOJ 1654: 이진 탐색, 이분 탐색 (Binary Search)

---

들어가기에 앞서

 

 이진 탐색이나 이분 탐색이나 영어로는 Binary Search로 같은 말이다.

 

 결국 데이터를 반으로 나누어가며 목푯값을 찾는 알고리즘이다. 여기서 말하는 데이터는 정렬된 배열을 말한다.

 

 정렬된 배열로 진행해야 하는 이유는 이진 탐색 원리에 있다.

 

 우선 시작점과 끝점을 가지고 중간점을 만든다. 중간값을 기준으로 원하는 값과 비교하여 탐색할 구간을 좁혀나간다. 원하는 값이 중간값보다 작으면 왼쪽 절반을 탐색하고, 더 크면 오른쪽 절반을 탐색한다.

 

 위 작업을 반복하다가 원하는 값을 찾거나 구간이 사라지면 종료한다.

---

 이진 탐색을 왜 사용할까?

 

 배열을 처음부터 끝까지 차례대로 탐색하는 방법을 선형 탐색이라고 한다. 배열의 길이가 N이라고 할 때, 최악의 경우 시간복잡도는 O(N)이다.

 

 반면, 이진 탐색은 계속해서 반으로 나누어가며 탐색하는 방법이다. 즉, 배열의 크기가 두 배로 늘더라도 탐색하는 횟수는 한 번만 늘어난다. 따라서 배열의 크기가 N일 때, 이진 탐색의 시간복잡도는 O(log N)이다.

---

Binary Search

public static int binarySearch(int[] arr, int target) {

    // 오름차순으로 정렬되지 않았다면 정렬 코드가 추가된다.

    int start = 0; // 시작점
    int end = arr.length - 1; // 끝점

    while (start <= end) {
        int mid = (start + end) / 2; // 중간점 (중간값)
        if (arr[mid] == target) {
            return mid; // 값을 찾으면 해당 인덱스를 반환
        } else if (arr[mid] < target) { // 타겟이 더 크면 오른쪽 절반 탐색
            start = mid + 1;
        } else { // 타겟이 더 작으면 왼쪽 절반 탐색
            end = mid - 1;
        }
    }
    return -1; // 값을 찾지 못하면 -1을 반환 (관례)
}

▶ 기본적인 이진 탐색 코드다.

▶ 만약 배열 내 중복된 값이 존재한다면 오차가 생길 수 있다.

▶ 특정 조건이 존재한다면 해당 조건에 맞게 코드를 수정해야 한다.

---

 일단 중복 원소가 있다는 가정 하에 Upper Bound와 Lower Bound를 구현해 보자.

 

Upper Bound

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 3, 3, 4, 5};
    int target = 3;

    int start = 0;
    int end = arr.length - 1;

    // Upper Bound: target 초과하는 첫 인덱스
    while (start < end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] <= target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
}

Lower Bound

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 3, 3, 4, 5};
    int target = 3;

    int start = 0;
    int end = arr.length - 1;

    // Lower Bound: target 이상인 첫 인덱스
    while (start < end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
}

---

---

 문제부터 이해하자.

 

 배열의 경우, 각 순회 단계에서 구해진 mid 값으로 arr[mid]와 target의 비교를 통해 start와 end를 좁혀나갔다.

 

 랜선 자르기 문제에서의 target은 입력으로 들어오는 N이고, 이는 만들고자 하는 랜선의 수다. 즉, 특정 개수에 대한 특정 길이를 찾는 문제다.

 

 참고로 이진 탐색에는 두 가지 방식이 존재한다. 첫째는 Upper Bound이고, 둘째는 Lower Bound이다. 상한은 target을 초과하는 첫 위치를 반환하고, 하한은 target 이상인 첫 위치를 반환한다.

 

 두 방식은 어떤 상황에서 다른 결과를 나타낼까? 그건 중복 값이 있을 때다.

 

 예를 들어 배열이 {1, 2, 3, 3, 3, 4, 5}인데 target이 3이라고 가정하자. 상한 방식은 3을 초과하는 첫 위치인 arr[5], 즉 인덱스 5를 반환할 것이다. 반면 하한 방식은 3 이상인 첫 위치로 arr[2], 즉 인덱스 2를 반환할 것이다.

 

 이 내용을 요약하자면 이렇다. 특정 조건이 중복 원소 내 가장 큰 값이라면, 상한 - 1을 하면 된다. 특정 조건이 중복 원소 내 가장 작은 값이라면, 하한 그대로 사용하면 된다.

 

 돌아와서, 지금 target은 중복될 확률이 매우 높은 '랜선의 수'이고, 가장 긴 케이스를 원한다. 랜선의 수가 중복될 때 최대 길이를 찾는 것, 즉 상한 방식을 따라야 한다.

---

 이제 랜선 자르기 문제를 구현해 보자.

 

Problem 1654

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Problem1654 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[K]; // 보유한 랜선의 길이

        long min = 1; // 랜선의 최소 길이 1cm
        long max = 0;

        // 입력과 동시에 보유한 랜선의 최대 길이 (max) 갱신
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        while (min < max) {
            long mid = min + (max - min) / 2;
            long count = 0;

            for (int i : arr) {
                count += i / mid;
            }

            if (count < N) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        System.out.println(min - 1); // Upper Bound 방식이므로, min - 1
    }
}

[틀린 코드]

Problem 1654

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Problem1654 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[K]; // 보유한 랜선의 길이

        long min = 1; // 랜선의 최소 길이 1cm
        long max = 0;

        // 입력과 동시에 보유한 랜선의 최대 길이 (max) 갱신
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }

        while (min <= max) {
            long mid = min + (max - min) / 2;
            long count = 0;

            for (int i : arr) {
                count += i / mid;
            }

            if (count < N) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }

        System.out.println(max); // Upper Bound 방식이므로, max
    }
}

[맞는 코드]

---

 근데 틀렸다.. 코드를 조금 수정하니 해결되긴 했으나 정확한 원인을 아직 잘 모르겠다. 이해하는 대로 원인을 업데이트하도록 하겠다.

---