코드숨 알고리즘 day05 이진탐색
코드숨 알고리즘 for 코딩 테스트 - DAY5 : 이진탐색
수 찾기
다음과 같은 아이디어를 생각했다.
- 입력 리스트에 존재하는지 in이면 1 not in 이면 0
- 입력 리스트를 정렬하여 중간 값부터 점검 (이진탐색)
그래서 먼저 존재하는지 알려주는 함수를 만들고 테스트했다.
def is_exist(target, numbers):
"""
numbers에 target이 존재하면 True, 존재하지 않으면 False
:param target: 검사할 수
:param numbers: 대상 정수 리스트
:return: numbers에 target이 존재하면 True, 존재하지 않으면 False
"""
return target in numbers
def test_is_exist():
assert is_exist(1, [1, 2, 3]) == True
assert is_exist(1, [4, 2, 3]) == False
test_is_exist()
그 다음 이진 탐색을 통해서 존재하는지 검사를 했다. 하나씩 반복해도 되지만 그러면 매우 비효율적이다. n번을 다 검사하게 되는데 이진 탐색을 이용하면 logn으로 줄어든다.
def binary_search(target, numbers):
"""
이진 탐색을 이용해서 numbers에 target이 존재하는지 검사
target보다 index 값이 더 크다면 index의 왼쪽에 target이 있는 것이므로 left_index와 index 중앙값으로 index 변경
target보다 index 값이 더 작다면 index의 오른쪽에 target이 있는 것이므로 right_index와 index 중앙값으로 index변경
left_index 가 right_index보다 커지면 없는거
:param target:
:param numbers:
:return: 존재하면 True, 존재하지 않으면 False
"""
left_index = 0
right_index = len(numbers) - 1
while True:
index = (left_index + right_index) // 2
if left_index > right_index:
return False
if target < numbers[index]:
right_index = index - 1
elif target > numbers[index]:
left_index = index + 1
elif target == numbers[index]:
return True
예산
- 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
- 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
1번 요건을 충족하기 위해 입력값의 총 액이 예산보다 적으면 예산의 가장 큰 금액을 반환 총 액이 예산보다 크다면 예산의 평균값, 최저값, 최댓값으로 이진탐색. 이 때 예산의 최댓값보다 예산이 적으면 그냥 합하고 크면 최댓값으로 만든다.
def get_budget(budgets, limit):
max_budget = max(budgets)
min_budget = 0
while min_budget <= max_budget:
mid_budget = (max_budget + min_budget) // 2
total = 0
for budget in budgets:
if budget > mid_budget:
total += mid_budget
else:
total += budget
if total <= limit:
min_budget = mid_budget + 1
else:
max_budget = mid_budget - 1
return max_budget
랜선 자르기
처음에 범위를 어떻게 잡아야할지 고민을 많이했다. 범위는 가장 긴 랜선부터 길이이기때문에 1까지로 정했다. 또 지정한 개수만큼 나와야하기 때문에 개수도 고려해줘야한다.
def max_cable(cables, n):
max_len = max(cables)
min_len = 1
count = 0
while min_len <= max_len or count < n:
mid_len = (max_len + min_len) // 2
count = 0
for cable in cables:
count += cable // mid_len
# 카운트가 n보다 크다는 것은 케이블 길이를 더 늘려도 된다는 말
if count >= n:
min_len = mid_len + 1
elif count < n:
max_len = mid_len - 1
return max_len
후기
이진탐색은 범위를 어디서부터 어디로 설정할 것인지, 반복문의 중지조건을 어떻게 잡을 것인지 정하는 부분이 잘못 접근하면 많이 힘들어지는거 같다. 랜선자르기도 처음에는 가장 작은 케이블부터 생각을 했지만 작은 케이블에서 굳이 안써도 되는 경우도 있기 때문에 가장 큰 케이블로 범위를 변경했다.