랜선 자르기
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
나의 코드
import sys
input = sys.stdin.readline
n ,k = map(int, input().split())
arr = []
for _ in range(n):
arr.append(int(input()))
arr = sorted(arr)
start = arr[0]
result = []
while True:
cnt = 0
if start <= 0:
break
for i in range(n):
cnt += arr[i] // start
if cnt >= k:
print(start)
break
start -= 1이진탐색
최적화 문제
mid 설정
start, end로 범위 좁혀가면서 탐색
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
# 이진 탐색을 위한 초기 설정
start = 1
end = max(arr)
# 이진 탐색 실행
while start <= end:
mid = (start + end) // 2 # 중간 길이
cnt = sum(lan // mid for lan in arr) # 중간 길이로 만들 수 있는 랜선의 수
if cnt >= k: # 충분한 수의 랜선을 만들 수 있는 경우
result = mid # 현재 길이를 결과로 저장
start = mid + 1 # 더 긴 길이 탐색
else: # 부족한 경우
end = mid - 1 # 더 짧은 길이 탐색
print(result)
🥨 TIL
이진탐색
이진 탐색(Binary Search)을 사용하는 이유는 크게 두 가지입니다: 효율성과 대상 범위. 이진 탐색은 큰 데이터 집합에서 특정 값을 효율적으로 찾기 위한 알고리즘으로, 특히 정렬된 데이터에 매우 효과적입니다. 이진 탐색의 주요 장점을 자세히 설명하겠습니다:
-
시간 복잡도의 효율성:
- 일반적인 순차 탐색은 모든 요소를 순회하기 때문에 시간 복잡도가 O(N)입니다. 즉, 데이터가 많아질수록 탐색 시간이 선형적으로 증가합니다.
- 이진 탐색은 매 단계마다 탐색 범위를 반으로 줄입니다. 이로 인해 시간 복잡도는 O(log N)이 되며, 이는 데이터 양이 많아져도 탐색 시간이 로그 함수로만 증가한다는 것을 의미합니다. 따라서 매우 큰 데이터 집합에서도 빠르게 원하는 값을 찾을 수 있습니다.
-
적용 가능한 대상 범위:
이진 탐색은 최적화 문제나 결정 문제(예: 특정 조건을 만족하는 최대/최소 값 찾기)에 유용합니다. 이 경우, 목표 값이 존재하는 범위를 점차 좁혀가며 최적의 해를 찾을 수 있습니다.- 특히,
탐색 대상이 숫자 범위와 같이 연속적이거나 대규모 데이터 집합인 경우에 적합합니다.
예를 들어, 랜선 자르기 문제에서 최대 랜선 길이를 찾는 경우, 가능한 길이의 범위가 매우 넓을 수 있습니다. 이진 탐색을 사용하면, 가능한 길이 범위를 절반씩 줄여가며 빠르게 최적의 길이를 찾을 수 있습니다. 이는 순차적으로 모든 가능한 길이를 검사하는 것보다 훨씬 더 효율적이며, 큰 데이터 세트에서 탐색 시간을 크게 단축시킵니다.
