[백준]이진 탐색

쟈니·2023년 1월 19일

코딩테스트/알고리즘

목록 보기

9/34

백준 2343 : 기타레슨

def add_lesson():
    cnt = 0  # 레코드 갯수 세기
    sum_lesson = 0  # 한 레코드에 들어갈 레슨들의 합
    for i in range(N):
        if sum_lesson + lesson_list[i] > mid:
            cnt += 1
            sum_lesson = 0
        sum_lesson += lesson_list[i]
        print(sum_lesson)
        print(i)
        print(mid)
        #감이 오지 않아, sum, 인덱스번호와 중간값을 출력하여 확인하였음
    else:
        if sum_lesson:
            cnt += 1
    return cnt


if __name__ == "__main__":
    N, M = map(int, input().split())  # N: 레슨 수, M: 블루레이 수
    lesson_list = list(map(int, input().split()))  # 레슨들

    right = sum(lesson_list)   # 레슨을 하나의 레코드에 다 담을 수 있을 때 레코드의 크기는 레슨의 합이다
    left = max(lesson_list)  # 레코드가 가질 수 있는 가장 작은 크기
    while left <= right:
        # 레코드 크기 중간값 구하기
        mid = (left + right) // 2
        cnt = add_lesson()
        if cnt <= M:  # 레코드 숫자가 모자라면 레코드 크기(mid)를 줄인다.
            right = mid - 1
        elif cnt > M:  # 레코드 숫자가 더 많아지면 레코드 크기(mid)를 늘린다
            left = mid + 1

    # 답은 left 에 있다. (최소 크기)
    print(left)

참고한 코드

접근방식

후기

이진 탐색은 무엇을 구해야 하는가 와 무엇을 기준으로 이진 탐색을 진행해야 하는지를 잘 찾아야 한다.
위 문제에서는 블루레이의 최소 크기를 구하고, 블루레이의 크기를 블루레이의 갯수 기준으로 이진탐색을 진행하였다.

백준 11687 : 팩토리얼 0의 개수

def facto(n):
    zeros = 0
    while n >= 5:
        zeros += n // 5
        n //= 5
    return zeros


m = int(input())
left, right, result = 1, m * 5, 0

while left <= right:
    mid = (left + right) // 2

    zero_count = facto(mid)


    if zero_count < m:
        left = mid + 1
        #m=3일때, zero_count = 2, left = 9
    else:
        right = mid - 1
       #m=3일때, zero_count = 3, right = 11
        result = mid
        #mid = 10

print(result if facto(result) == m else -1)

참고한 코드

후기

팩토리얼 부터 작성해보았는데, 애초에 팩토리얼 문제구나 생각하면 안되고 오른쪽에 위치한 0의 개수가 메인이다! 그렇기 때문에 math라이브러리에서 제공하는 팩토리얼 함수를 꼭 쓸 필요가 없다.
왜 이 문제를 꼭 이진탐색으로 풀어야 할까라는 생각이 있었는데, 제한시간이 매우 짧아 이진탐색을 사용한다는 것을 알게 되었다.~~(시간이 짧게 든다면 조건문으로 5, 15, 25로 나누었을 때로 구분하여 답을 구할 수 있다.)~~

백준 1920 : 수 찾기

N = int(input())
target_list = sorted(list(map(int, input().split())))
M = int(input())
search_list = sorted(list(map(int, input().split())))
def searching_z(target):
      target = target_list[i]
      left, right = 0, N - 1
      while left <= right:
            mid = (left + right) // 2
            if mid == target:
                return 1

            elif target <= mid:
                right = mid -1
            else:
               left = mid +1

for i in range(M):
    if searching_z(search_list[i]):
        print(1)
    else:
        print(0)