[이것이 코딩테스트다] 16일차 - 이진탐색 예제풀이

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 7 이진탐색

오늘 풀이한 문제 - 이진탐색 예제

[이코테 197p] 부품찾기

문제

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

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

N=5
[8, 3, 7, 9, 2]
손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3
[5, 7, 9]
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

 

접근방법

지금 이진탐색을 배우고있어서 그런지 이진탐색으로 풀어야겠다는 생각만 했다

다른 풀이방법으로 리스트에 요소가 있는지 검사하여 푸는 방법도 있었다!

 

소스코드

## 재귀함수 이용 (이진탐색)
def binary_search(start, end, data, target):
    mid = (start+end)//2
    if start >end:
        return None
    
    if data[mid] == target:
        return mid
    elif data[mid] > target:
        return binary_search(start, mid-1, data, target)
    else:
        return binary_search(mid+1, end, data, target)
        
N = 5
have = [8,3,7,9,2]

M=3
req = [5,7,9]

for target in req:
    r = binary_search(0,len(have)-1,have, target)
    if r == None:
        print ('no', end = ' ')
    else:
        print ('yes', end = ' ')

## 요소 검사하며 풀기
N = 5
have = [8,3,7,9,2]

M=3
req = [5,7,9]

for target in req:
    if target in have:
        print ('yes', end = ' ')
    else:
        print ('no', end = ' ')

 

[이코테 201p] 떡볶이 떡 만들기

문제

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다.
오늘은 떡볶이 떡을 만드는 날입니다.
동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다.
대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다.

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다.
높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다.

예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다.
잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다.
손님은 6cm만큼의 길이를 가져갑니다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하세요

- H는 10억보다 작거나 같은 양의정수이거나 0이다

 

접근방법

재귀함수를 만들어 풀으려 했지만 반복문을 사용하는것이 더 간단해서 반복문으로 풀이했다

마지막에 '적어도 M만큼의 떡을 얻기위해'라는 조건을 제대로 안읽어서 시간이 조금 걸렸다 

 

시작점 = 0, 끝점 = 가장 긴 떡의 길이

길이를 절단해가며 남은 떡의 길이를 보고, 

적어도 M길이만큼이라고 했으므로 M<절단된 떡의 길이일때마다 결과를 갱신한다

 

소스코드

n,m = 4,6
dduk = [19, 15,10,17]

start = 0
end = max(dduk)

result = 0
while (start<=end):
    tmp = 0
    mid = (start+end)//2
    for ddu in dduk:
        if ddu > mid:
            tmp += (ddu - mid)
    if tmp >= m:
        result = mid
        start = mid+1
    else:
        end = mid-1

result # 15

 

이러한 유형의 문제를 파라메트릭 서치(Parametric Search) 유형이라 부른다고한다. 

파라메트릭 서치는 최적화 문제를 예/아니오(결정문제)로 바꾸어 해결하는 기법으로 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제를 풀때 이용한다

이 문제의 H 범위를 보고 이진탐색을 떠올릴 수 있어야한다. 

 

연습문제 풀이는 깃허브에도 업로드 되어있습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)