[백준][2343] python - 기타레슨문제로 알아보는 이분탐색과 파라미터 탐색

이분탐색

정렬되어 있는 배열에서 찾고자 하는 x를 가지고 배열을 둘로 나누어가면서(이분) 탐색하는 방법

정렬의 특성을 극대화한 알고리즘이다.

 

만약 N길이의 배열에서 x이하의 가장 큰 수를 찾는다는 문제가 있을 때

배열의 모든요소를 하나씩 탐색한다면 최대 시간복잡도는 O(N)이 나올 것이다.

하지만 이분탐색을 이용하면 처음부터 끝까지 순차적으로 배열을 탐색하지 않고,

탐색 시작지점(L, Left)과 끝지점(R, Right)을 설정해서 중간지점(mid)을 탐색하여 빠르게 탐색한다.

만약 중간지점의 값이 x이상이라면 그 이후의 값들은 고려할 필요가 없어진다. 반대로 x이하라면 그 이전의 값들을 고려할 필요가 없어진다.

이를 보장하기 위해서는 배열이 정렬되어있어야한다.

 

그러면 탐색의 끝지점(R)을 중간지점의 바로 앞으로 옮겨서(mid -1) 같은 방법을 계속해서 탐색하다보면 빠르게 원하는 값을 찾을 수 있다.

일반적인 풀이방법

L, R, Result, x(조건) 을 설정해서 L이 R보다 작거나 같은 조건에서 계속해서 탐색한다.

def lower_bound(a, L, R, x):  # 배열, Left, Right, 탐색할 목표
    res = R + 1
    while L <= R:
        mid = (L + R) // 2
        if a[mid] >= x:
            res = mid
            R = mid - 1
        else:
            L = mid + 1
    return res  # 탐색 결과의 인덱스

이분탐색 문제 : 7795 먹을 것인가 먹힐 것인가

 

매개변수 탐색

이분탐색을 활용한 방식으로 문제를 찾고자 하는 정답을 매개변수로 만들고 결정문제로 바꾸어 푸는 방법

결정문제란
어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 
https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95_%EB%AC%B8%EC%A0%9C

 

결정문제는 간단히 말해 Yes/No로 대답할 수 있는 문제라고 이해했다.

결정문제로 뒤집어 문제를 생각했을 때 더 쉽고 빠르게 풀 수 있는 문제에 적용할 수 있다.

주로 이런 문제에는 ~~의 최댓값 또는 최솟값을 구하라는 문제가 나올 수 있다.

 

정답을 매개변수로 만들고라는 말이 잘 이해가 안되었는데

1. 정답을 결정문제의 매개변수로 만든다.

2. 이분탐색에서 탐색되는 배열이 정답의 범위를 나타낸다. 

두 가지로 바꾸어 이해했다.

 

예제 : 기타레슨

알고리즘 분류가 이분탐색, 매개변수 탐색인 문제이다

2343번: 기타 레슨

N : 강의의 개수

M : 블루레이의 개수

 

N개의 강의를 M개의 블루레이로 나누어 녹화할 때 가능한 블루레이 크기 중 최소 크기는?를 구하는 문제를

크기 S의 블루레이를 M개 만든다면 모든 강의를 녹화할 수 있는가?

문제로 바꾸어 생각해보았다.

 

1. 주어지는 강의의 순서는 유지되면서 블루레이를 만들어야한다.

2. 블루레이의 최소 사이즈는 주어지는 강의들 중의 가장 긴 강의이다.

3. 블루레이의 최대 사이즈는 N * 강의의 최대 길이 (10,000)이다.

위 세 가지 조건에 유의하면서 문제를 풀었다.

 

L, R의 초기값을 적절하게 설정해주는 것이 필요하다.

문제를 풀면서 2번 조건을 생각하지 못하고 풀었을 때 '틀렸습니다' 결과를 받았다.

L = 0으로 두고 풀었는데 아래 케이스에서 틀린 답을 얻었다.

2 2
10 1000

1000이 나와야 하는데 10이 나왔다.

위의 케이스에서는 정답값으로 가질 수 있는 블루레이의 최소 크기는 1000이다.

즉, 1000에서부터 정답을 탐색해야한다는 것!

 

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
lessons = list(map(int, input().split()))


def determination(S):
    global M
    curr_size, cnt = 0, 1
    for l in lessons:
        if curr_size + l > S:
            cnt += 1
            curr_size = 0
        curr_size += l
    return cnt <= M


L, R = max(lessons), N * 10000
res = R
while L <= R:
    mid = (L + R) // 2
    if determination(mid):
        res = mid
        R = mid - 1
    else:
        L = mid + 1
print(res)