이진 탐색

이진 탐색 / 이분 탐색 (Binary Search) 이진 탐색 (이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색 은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 이진 탐색 / 이분 탐색 알고리즘 코드 (Python) # 재귀 함수로 구현한 이진 탐색 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 원하는 ..

array1에 있는 데이터중, array2에 있는 데이터와 일치하는 데이터가 있는지 판단하고, array2에 있는 데이터가 각 데이터별로 몇개가 array1에 존재하는지 구하는 문제 유형이었다. 우선, 데이터 탐색 범위가 거의 20000000개 이기 때문에, Binary Search를 이용해야 한다고 판단했다. 그래서 처음 시도한 방법은, 기본적인 Binary Search로 데이터 탐색 후에, 이진탐색 하며 나온 데이터 중, 미리 지정해둔 데이터가 몇 개 나왔는지 count()를 사용해서 tmp리스트에 인덱스 순서대로 기록하는 방식으로 풀이를 시도했는데, 구하고자하는 결과는 잘 도출이 되었지만, 시간초과문제가 발생했다. 이진 탐색과정에서는 문제가 없었는데, 데이터를 기록하려고 작성한 for문에 들어간 c..

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

민교네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 민교는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를 , 없으면 no를 출력한다. 구분은 공백으로 한다. [입력 조건] 첫째 줄에 정수..