[이코테] 이분탐색, 파라메트릭 써치, 부품 찾기, 떡볶이 떡 만들기

이분 탐색

**이분 탐색(Binary Search)**는 정렬된 데이터에서 특정 값을 효율적으로 찾기 위해 사용하는 알고리즘이다.
데이터를 절반씩 나누어 탐색 범위를 좁혀가며, 시간 복잡도가 O(\log N\)인 효율적인 방법이다.

 

값의 범위가 0~10 까지이고, 만약 찾고자 하는 값이 3 이라 하면 아래와 같은 방식으로 이뤄진다.

1. 중간값을 구한다.

2. 중간값보다 찾는 값이 작으면, 범위를 시작값 ~ 중간값 -1 으로 재조정한다.

3. 중간값보다 찾는 값이 크면, 범위를 중간값+ 1 ~ 마지막값 으로 재조정한다.

4. 중간값이 찾는 값과 같을 때까지 1~3을 반복한다.

 

재귀와 반복문 둘 중 하나로 구현 가능하다.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # 값을 찾지 못함

arr = [2, 4, 7, 10, 15, 20]
print(binary_search(arr, 10))  # 출력: 3

def bs_search(start, end, target) :
    mid = (start + end) // 2
    if(start <= end): 
        if(arr[mid] == target): return mid
        elif(arr[mid] < target):
            return bs_search(mid + 1, end, target)
        else:
            return bs_search(start, mid - 1, target)
    else:
        return False
    
print(bs_search(0, 5, 10))  # 출력: 3

파라메트릭 써치

파라메트릭 서치는 "특정 조건을 만족하는 값이 존재하는가?"를 판단하는 문제를 기반으로, 그 값의 범위를 이진 탐색하여 최적의 값을 효율적으로 찾는 방법이다. 즉 최적화 문제 -> 결정문제 로 만들고, 값을 찾기 위해 이분탐색을 활용하는것.

 

특정 조건을 만족하는 최적화된 N 값을 도출한다. [최적화 문제]

범위 N이 특정 조건을 만족하는가? [결정 문제]

 

최적화 문제: 어떤 조건을 만족하는 최대, 최소값을 구하는 문제

결정 문제: 답이 Y/N으로 갈리는 문제

 

전체 값이 될 수 있는 후보들 A~Z 중

A,B,C,E,D 가 조건에 맞니? -> YES

A,B,C 가 조건에 맞니? -> NO

E,D 가 조건에 맞니? -> YES
E 가 조건에 맞니? -> YES

D 가 조건에 맞니? -> NO

 

이런 식으로 이진탐색을 이용해 범위를 좁혀가면서 답을 찾아가는 방식이다.

 

문제 01 부품 찾기

문제 내용

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

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N = 5
[8, 3, 7, 9, 2]
손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.
M = 3
[5, 7, 9]
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes룰, 없으면 no 를 출력한다. 구분은 공백으로 한다.

 

문제 풀이

일단 이진탐색을 하려면 값이 정렬되어 있으므로 정렬 부터 한 다음, 이진 탐색을 통해 값을 찾아낸다.

N, M = map(int,input().split())
goods = sorted(list(map(int,input().split())))
orders = sorted(list(map(int,input().split())))
def bs_search(start, end, target) :
    mid = (start + end) // 2
    if(start <= end): 
        if(goods[mid] == target): return True
        elif(goods[mid] < target):
            return bs_search(mid + 1, end, target)
        else:
            return bs_search(start, mid - 1, target)
    else:
        return False

for item in range(0,M):
    print(orders[item], ' :: ' , bs_search(0, N, orders[item]))
# 5 3
# 8 3 7 9 2
# 5 7 9

 

문제 02 떡볶이 떡 만들기

문제 내용

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

손님이 요청한 길이가 M일 때 적어도 M을 가져갈 수 있는 절단기의 최대 높이를 구하시오.

 

문제 풀이

특정 범위가 해당 조건을 만족하는가? 를 주안점으로 문제를 풀도록 한다.

이 때 범위를 잡는 방식을 이분탐색을 이용한다. (파라메트릭 써치)

그리고 문제 내용을 보면 적어도 M을 가져가야 하는 것이기 때문에, 손님이 가져갈 분량이 M을 넘을 때에도 답을 갱신해 두어야 한다.

4 1

1 1 1 1

--> 답 0

다만 이코테 책에 반례들이 없어서.. 이게 모든경우를 다 통과할지는 모르겠다;

# 4 6
# 19 15 10 21
# 나머지가 6이 될 수 있는 절단기 높이 H의 최댓값.

N, M = list(map(int,input().split()))
cakes = list(map(int,input().split()))
mx = max(cakes)
cut = 0
ans = 0
def isTarget(mid):
    global N
    total = 0 # 손님이 가져갈 분량
    for c in range(0, N):
        cake = cakes[c]
        total += (cake - mid) if cake > mid else 0
    ret = 1
    if(total > M): ret = 2
    elif(total < M): ret = 3
    return ret

while True:
    mid = (cut + mx) // 2
    succed = isTarget(mid)
    if(succed == 1):
        ans = mid # 혹시나 딱 맞게 되면 갱신후 바로 종료
        break
    elif(succed == 2):
        ans = mid # 최대한 덜 잘랐을 때가 정답이라 일단 갱신
        cut = mid + 1
    else:
        mx = mid - 1
    if(cut > mx): 
        break
print('ans', ans)