이번주 알고리즘은 이분 탐색이다! 이진 탐색 이라고 부르기도 한다
학교 알고리즘 수업 시간에 배웠던 기억이 있다

이분 탐색(Binary Search)

이분 탐색은 오름차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법이다
대부분의 알고리즘들과 다르게 정렬이 되어 있어야 사용할 수 있다
순차적 탐색 보다 빠른 탐색을 위해 나온 방법으로 이분 탐색의 시간복잡도가 순차적 탐색 보다 낮다

• 순차적 탐색
  • 정렬된 배열 안에서 특정 원소를 찾기 위해 처음부터 차례대로 탐색
  • 원소를 건너뛰지 않고 순서대로 탐색함

다시 돌아와서 이분 탐색에 대해서 좀 더 설명해보자면 정렬되어 있는 배열을 가운데에 위치한 값을 활용해서 탐색하는 것이다

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} 이라는 배열이 있다고 가정해보자

이 때 7을 찾고 싶다고 해보자

순차적 탐색 으로 찾게 되면

1 → 2 → 3 → 4 → 5 → 6 → 7

이런 순서대로 찾게 된다

이진 탐색 으로 찾게 되면 가운데에 있는 6으로 가고 찾으려는 7이 6보다 크니까 오른쪽을 찾게 된다
그럼 다음에 찾게 될 배열은 {7, 8, 9, 10, 11} 이 되고 이 배열의 중앙값인 9보다 작으니 배열은 다시 {7,8}이 된다
이제 여기서는 mid 값을 어떻게 했느냐에 따라 달라지는데 -1 을 했으면 바로 7이 나오게 되고 +1이면 8이 나와 그 다음 차례에 7을 찾게 된다

6 → 9 → 7

순차적 탐색은 찾으려는 값이 배열의 맨 마지막에 있을 경우 끝까지 탐색해야 해서 시간복잡도는 O(n)이다
이분 탐색은 한번 탐색할 때마다 범위가 반씩 줄어서 시간복잡도는 O(log n)이다

개념은 크게 어려운 부분이 없으니 이제 문제를 한 번 풀어보자

백준 6236번 : 용돈 관리

문제 제목을 보고 이번달 용돈을 아직 안받은게 생각났다!
눈치를 슥 보면서 말을 해봐야겟다

암튼 문제를 보자!

문제

앞으로 N일 동안 사용할 금액 계산
M번만 통장에서 돈을 뺴서 사용
K원을 인출하고, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용, 모자라면 남은 금액은 통장에 넣고 다시 K원 인출 → ??
정확히 M번을 맞추기 위해 남은 금액이 그날 사용할 금액보다 많아도 남은 금액은 통장에 집어넣고 다시 K원 인출 - 인출 금액 K 최소화

입력

1번째 줄 : N과 M이 공백으로 주어짐
2번째 줄 : 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어짐

출력

현우가 통장에서 인출해야 할 최소 금액 K 출력

풀이

일단 문제 설명이 어렵게 되어 있는 것 같다

M번 출금하도록 정확하게 맞춰야하고, 그 중에서 제일 작은 값을 찾아야 한다

package baekjun.binarysearch;

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

public class P6236 {
    private static int[] money;
    private static int m;

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

        int n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        money = new int[n];

        for (int i = 0; i < n; i++) {
            money[i] = Integer.parseInt(br.readLine());
        }

        int start = Arrays.stream(money).max().getAsInt();
        int totalSum = Arrays.stream(money).sum();  // 모든 지출 합
        int end = totalSum; // 모든 지출의 합을 최댓값으로

        System.out.println(binarySearch(start, end));
    }

    private static int binarySearch(int start, int end) {
        int answer = end;

        while (start <= end) {
            int mid = (start + end) / 2;
            int count = findMoney(mid);

            if (count <= m) {       // 출금횟수가 m보다 작거나 같으면 좌측 탐색
                answer = mid;
                end = mid - 1;
            } else {                // 출금횟수가 m보다 크면 우측 탐색
                start = mid + 1;
            }
        }

        return answer;
    }

    private static int findMoney(int k) {
        int count = 1;
        int remain = k;

        for (int j : money) {
            if (remain < j) {
                count++;
                remain = k;
            }
            remain -= j;
        }

        return count;
    }
}

binarySearch(int start, int end) 안에서 findMoney(int k) 함수를 실행시킨다

findMoney(int k) 함수는 k라는 금액으로 인출한다고 가정했을 때의 출금 횟수를 계산하는 함수이다
이렇게 찾은 출금횟수가 m보다 작거나 같으면 더 작은 출금횟수가 있을 수 있으니 왼쪽을 탐색해준다.
근데 m보다 크면 우측 탐색을 해서(돈을 더 크게해서) 출금횟수를 줄이는 쪽으로 탐색을 해준다

후기

이번에는 나의 생각이 80퍼센트정도 들어간 것 같다!
실버1 문제라 그런가 골드보다는 나은 느낌...
근데 처음에 이분 탐색을 어떻게 적용할 지 고민을 좀 했었는데 그래도 나름 성공한 것 같다
최악의 경우를 고려하여 end를 모든 돈의 합으로 해야되는 부분에서 좀 헤맸던 것 같다