서강덕

코린이의 개발 성장기📝

탐색

탐색이란 리스트 내에서 데이터를 찾는 작업을 말한다. 흔히 탐색 방법으로는 순차 탐색이 있는데 말 그대로 첫번째 인덱스부터 차례대로 확인하는 방법인다. 반복문을 통해 N개의 데이터를 확인하기때문에 복잡도는 O(N)이다.

이진 탐색

이진 탐색은 범위를 절반씩 좁혀가면서 확인하는 방법으로 데이터가 정렬 되어있어야만 사용 가능한 알고리즘이다. 또한 탐색에 필요한 변수 3개가 있다.

  • 시작점
  • 끝점
  • 중간점
  1. 시작점을 index 0, 끝점을 index N-1, 중간점을 (시작점 + 끝점) // 2로 변수를 설정한다.
  2. 찾고자하는 target 데이터가 중간점보다 작은 경우 새로운 끝점을 기존 중간점-1로 옮기고 새로운 중간점을 계산한다.
  3. 찾고자하는 target 데이터가 중간점보다 큰 경우 새로운 시작점을 기존 중간점+1로 옮기고 새로운 중간점을 계산한다.
  4. 2,3 단계를 반복하면서 중간점과 target이 같은 경우 종료한다.

시간 복잡도

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 복잡도가 O(logN)이다.

예제

부품 찾기

문제

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

입력 조건

  • 첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)
  • 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
  • 셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)
  • 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

출력 조건

첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다

해결 방법

먼저 입력받은 데이터를 정렬하고 이진 탐색을 수행하면 된다.

import sys

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

N = int(sys.stdin.readline())
parts_num = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
check_num = list(map(int, sys.stdin.readline().split()))

parts_num.sort()

for i in check_num:
    result = binary_search(parts_num,i,0,N-1)
    if result == None:
        print('no',end=' ')
    else:
        print('yes',end=' ')

떡볶이 떡 만들기

문제

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1<=N<=1,000,000, 1<=M<=2,000,000,000)
  • 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

해결 방법

이 문제는 이진 탐색 문제이자, 파라메트릭 서치 한국말로하면 매개 변수 탐색 문제이다.
매개 변수 탐색은 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 여기서 결정 문제란 예 or 아니오로 답하는 문제를 말한다. 적절한 높이를 설정하고 조건을 만족하는지 확인하여 여부에 따라서 탐색 범위를 좁혀 나가면 된다.

import sys

N, M = map(int, sys.stdin.readline().split())

tteok = list(map(int, sys.stdin.readline().split()))

start = 0
end = max(tteok)
result = 0

while start <= end:
    total = 0
    mid = (start + end) // 2

    for x in tteok:
        if x > mid:
            total += x - mid
    if total < M:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

Comments