이진 탐색

[이것이 코딩 테스트다 with Python] 떡볶이 떡 만들기 : 이진 탐색

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 7 이진 탐색 실전문제 7-2 떡볶이 떡 만들기 201p 문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 이걸 처리 안 해줘서 시간을 허비했다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것..

[이것이 코딩 테스트다 with Python] 부품 찾기 : 이진 탐색

교재 : 이것이 코딩 테스트다 with 파이썬 CHAPTER 7 이진 탐색 실전문제 7-2 부품 찾기 197p 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품..

이진 탐색 알고리즘

이진 탐색(Binary Search) 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 시간 복잡도는 $O(logn)$을 가진다. ✔ 이진 탐색 과정 1. 데이터 집합(배열)의 중앙 요소를 선택합니다. 중간값 : 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 여기서 target = 9 로 한다. 2. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고, 반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다. 중앙값의 7과 비교하여 9가 더 크기 때문에 왼쪽을 지우고 오른쪽에서 중앙값을 구한다. 다시 구한 중앙값은 10이다. 3. 위의 2번을..