[이진 탐색] Chapter7 부품 찾기 & 떡볶이 떡 만들기

참고 출처 : 이것이 코딩테스트다 with 파이썬

---

# 부품 찾기

---

---

[이진탐색] : 재귀함수 이용할 것

 

1.

함수 인자에

리스트, 타겟, 0 (초기 start값), n-1 (end값)을

매개변수로 넘겨준다.

 

 

2.

def function 함수 

- start 값이 end보다 크면, None 값을 반환

- 만약 리스트[mid] 값이 target이랑 값이 같으면 mid를 반환한다.

- 만약 ... 크다면 function(리스트, 타켓, start, mid-1) => end 값이 mid-1로 변경

- 만약 ... 작다면 start 값이 mid+1로 변경

 

입력값 & 출력값

책 답지

1. 이진탐색 이용

---

#떡볶이 떡 만들기

---

=> 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제를 찾는 문제에 주로 파라메트릭 서치 사용

 

이 문제는 적절한 높이를 찾을때까지 절단기의 높이 H를 반복해서 조정하는 것

 

파라메트릭 서치 문제는 재귀적으로 구현하지 않고 반복문을 구현하면 간결하게 문제를 풀 수 있다.

 

중간점의 값은 시간이 지날수록 최적화된 값을 찾기 때문에,

과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을때마다

결괏값을 중간점 값으로 갱신해주면 된다.