[99클럽 코테 스터디 4일차 TIL] 이분 탐색

문제 : https://www.acmicpc.net/problem/2343

 

백준 2343번 기타 레슨

 

 

풀이

이분 탐색을 활용하는 방법

이진 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 입니다. 따라서 sort() 메서드를 사용하여 정렬을 우선 해줘야 합니다. 그리고 보통 변수 3개 (start, mid, end)를 사용하여 탐색하게 됩니다.

이분 탐색을 사용할 경우 시간 복잡도는 O(logN)입니다. 단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 O(logN)이라는 시간 복잡도를 가지게 됩니다. 

import sys

read = sys.stdin.readline

N, M = map(int, read().split())
data = list(map(int, read().split()))

# 이분 탐색 값 초기화
start = max(data)
end = sum(data)
answer = 0

while start <= end:
    mid = (start + end)//2
    count = 1
    sum_value = 0
    for i in data:
        if sum_value + i <= mid:
            sum_value += i
        else:
            count +=1
            sum_value = i
    if count > M:
        start = mid + 1
    else:
        answer = mid
        end = mid - 1
print(answer)

 

TIL

오늘도 역시나 이분 탐색을 사용하여 푸는 문제 였습니다. 다만, 이분 탐색의 초기 값을 설정하는 것에 생각보다 애를 먹었습니다. 처음에는 단순히 start = 0, end = sum(data)로 설정했었는데, 틀렸습니다~ 라는 문구가 나와서.. 어 ? 머가 틀렸지 라는 생각이 들어서 계속 고민을 했습니다.

=> min(data)는 리스트의 최솟값을 의미하며, 이는 그룹 하나에 포함될 수 있는 최소값입니다. 하지만 문제에서 요구하는 것은 그룹의 합의 최댓값을 최소화하는 것이므로, 이 값은 탐색의 시작점으로 적합하지 않습니다. 따라서 가능한 한 최소값을 가져야하는 start는 max(data)가 되어야 합니다.

 

이 외에도 다른 방법이 있다면 정보를 공유해주시면 감사하겠습니다.