1. 블루레이 만들기
이진 탐색 알고리즘은 주어진 배열에서 단순히 값을 찾아내기 위한 용도뿐 아니라, 위 문제에서처럼 가장 적절한 값을 탐색하기 위한 용도로도 자주 활용된다. 블루레이의 사이즈가 너무 크면 줄이고, 너무 작으면 늘리는 과정을 통해 최종적으로 최적의 사이즈를 찾아내는 것이다.
이와 같은 방식을 편의상 최적해 이진 탐색이라고 칭하겠다. 최적해 이진 탐색을 수학적으로 표현하면, 증가함수 f(x)에 대하여 f(x) ≥ T를 만족하는 x의 최소 값을 찾는 과정(또는 감소 함수 f(x)에 대하여 f(x) ≥ T를 만족하는 x의 최대 값을 찾는 과정)이라 할 수 있다. 이 때, f(x)가 증가함수여야 하는 이유는, 이진 탐색이 정렬을 전제하는 알고리즘이기 때문이다. 최적해 이진 탐색은 기존에 배웠던 이진 탐색과 조금 다른 특징을 갖는다.
- 기존 이진 탐색: 값을 찾는 경우는 반드시 아래의 두 가지 경우 중 하나이다.
- 우연히 mid 값이 찾는 값과 동일한 경우
- start, mid, end 값이 동일한 경우
- 최적해 이진 탐색
- f(x) ≥ T를 만족하는 x의 최소 값을 찾는 문제: start와 end가 교차될 때, start에 해당하는 값이 최적해가 된다.
- f(x) ≥ T를 만족하는 x의 최대 값을 찾는 문제: start와 end가 교차될 때, end에 해당하는 값이 최적해가 된다.
최적해 이진 탐색에서 start 또는 end로 최적해가 결정되는 원리에 대해 간단히 설명하도록 하겠다. 이진 탐색에는 기본적으로 시작점과 끝점이 존재한다. 이 때, start는 x의 최소 값을, end는 x의 최대 값을 가리키게 된다. 이진 탐색이 반복적으로 수행되는 과정에서 최소 값과 최대 값의 범위는 점차 수렴될 것이며, start가 end를 추월할 때 이진 탐색이 종료된다.
처음에 start를 x의 최소 값을 가리키는 값으로 설정했기 때문에, 이진 탐색이 종료되었을 때 start 값은 f(x) ≥ T를 만족하는 x의 최소 값을 가리키게 된다. 반대로, f(x) ≥ T를 만족하는 x의 최대 값을 찾는 문제였다면, 처음에 end를 x의 최대 값을 가리키는 값으로 설정했기 때문에, end가 최적해를 가리키게 된다. 이러한 이유로, 각각 start와 end에서 최적해가 얻어지는 것이다.
배운 내용을 바탕으로 위 문제를 풀어보자. 위 문제에서 구하고자 하는 값은 블루레이의 사이즈이므로, 당연히 블루레이 사이즈의 최소 값과 최대 값을 각각 시작점과 끝점으로 설정해야 할 것이다. 즉, 제일 긴 강의의 시간이 최소 값, 모든 강의 길이의 총합이 최대 값이 된다. 그리고 이진 탐색이 종료되었을 때, start에 해당하는 값이 문제에서 요구하는 답이 될 것이다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
lst = list(map(int, input().split()))
start = max(lst) # 제일 긴 강의의 시간
end = sum(lst) # 모든 강의 길이의 총합
while start <= end:
sum = 0 # 강의 길이의 합
cnt = 0 # 사용된 블루레이의 개수
mid = (start + end) // 2
for i in range(N):
if sum + lst[i] > mid: # 블루레이의 사이즈를 초과할 경우
sum = lst[i] # 해당 레슨을 새로운 블루레이에 녹화
cnt += 1
else:
sum += lst[i] # 같은 블루레이에 계속해서 레슨 녹화
if sum != 0: # sum에 해당하는 길이의 강의를 녹화하기 위한 새로운 블루레이 필요
cnt += 1
if cnt > M: # 블루레이의 사이즈가 작음
start = mid + 1
else: # 블루레이의 사이즈가 큼(최적화 필요)
end = mid - 1
print(start) # start와 end가 교차될 때, start에 해당하는 값이 최적해2. 배열에서 K번째 수 찾기
언뜻 보기에는 A 배열을 이용해 B 배열을 생성하고, 이를 정렬하여 k번째 인덱스에 접근하면 되는 간단한 문제처럼 보인다. 그러나, 위 문제의 시간 제한은 2초, 메모리 제약은 128MB이며, N은 최대 10^5이다. 즉, 배열을 생성할 때 사용되는 이중 for 문에서 시간 초과가 발생할 가능성이 있으며, 메모리 초과 발생 가능성도 존재하기 때문에, 생각처럼 단순한 문제는 아니다.
위 문제가 단순하지 않은 이유는 N X N의 결과가 너무 크기 때문이다. 따라서, 이 부분에 대해 최적화를 진행해보기로 하자. (편의상 B[k]를 x로 표기하기로 한다.)
- N X N의 모든 원소를 다 고려할 필요 없이, x보다 작거나 같은 값만 고려해도 충분하다.
- 또한, x보다 작거나 같은 값에 대해 정렬을 수행할 필요 없이, 그저 개수만 알아내면 된다.
위 내용을 바탕으로 다시 문제를 분석해보자. k번째 수가 x라는 말은, x보다 작거나 같은 원소의 개수가 최소 k개 이상이라는 의미로 해석할 수 있다. 즉, 자기 자신보다 작거나 같은 수의 개수가 k개 이상인 원소들 중에서, 가장 작은 원소를 찾아내는 것이 목표인 것이다. (사실 이러한 해석을 해내는 과정이 이 문제에서 제일 어려운 부분이다.)
바로 이 부분에서 최적해 이진 탐색을 떠올릴 수 있다. 그 이유는 f(x)를 x보다 작거나 같은 수의 개수라고 정의하면, f(x)는 단조 증가하게 되는데, 이 때 f(x) ≥ k를 만족하는 x의 최소 값을 구해야 하기 때문이다.
이진 탐색을 이용하기로 결정했다면, 가장 먼저 해야 할 일은 start와 end의 값을 정하는 것이다. 쉽게 생각하면, start는 1로, end는 N X N으로 결정하면 된다. 실제로, 이진 탐색의 시간 복잡도는 O(logN)으로 매우 낮기 때문에, 시간 초과도 발생하지 않는다. 그러므로 이렇게 풀이해도 상관은 없지만, 참고할만한 한 가지 흥미로운 사실이 있다. 바로 k번째 수는 결단코 k보다 클 수 없다는 것이다. 이는 우리가 흔히 구구단 행렬이라고 부르는 이차원 행렬의 특징이다. 이는 x의 최대 값이 k라는 의미이므로, end를 k로 설정하여 최적화할 수 있다.
마지막으로 해야 할 일은, x보다 작거나 같은 수의 개수를 어떻게 알아낼 것인지 생각해보는 것이다. 사실 구구단 행렬에는 흥미로운 특징이 하나 더 있다. 바로, i번째 행에서 x보다 작거나 같은 수의 개수는 x // i가 된다는 것이다. 사실 너무나도 당연한 것이, i * n <= x (n = 1, 2, 3, ...)에서 n이 개수를 의미하기 때문이다. 다만 주의해야 할 것은, x // i는 n의 상한 값일 뿐이기 때문에 N보다 커질 수 있다는 것이다. (이 내용에 대해서는 아래의 그림을 참고하기 바란다.) 따라서, x // i와 N 중 더 작은 값을 선택하여 x보다 작거나 같은 수의 개수를 계산해야 한다.
사실 이 문제는 문제 풀이 방법을 생각하는 것은 매우 어려우면서도, 구현 코드는 매우 간단하다.
import sys
input = sys.stdin.readline
N = int(input())
k = int(input())
start = 1
end = N * N # end = k로 최적화 가능
while start <= end:
mid = (start + end) // 2
cnt = 0 # x보다 작거나 같은 수의 개수
for i in range(1, N + 1): # 행렬의 각 행을 순회
cnt += min(mid // i, N)
if cnt < k: # x보다 작거나 같은 원소의 개수가 k개 미만
start = mid + 1
else: # x보다 작거나 같은 원소의 개수가 최소 k개 이상
end = mid - 1
print(start)단조 증가 함수에서 최소 값을 찾는 문제이므로, 마찬가지로 start에 해당하는 값이 최적해가 된다.
