성덕이의 개발공간

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 시간 복잡도를 O(logN)으로 동작하는 알고리즘을 요구하므로 선형 탐색이 아닌 이진 탐색을 수행 데이터가 정렬되어 있기 때문에 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산하여 답을 도출 4. 소스 코드 from bisect import bisect_left, bisect_right # 값이 [left_value, right_balue]인 데이터의 개수를 반환하는 함수 def count_by_range(a, left_value, right_value): right_index = bisect_right(a, right_value) left_index = bisect_left(a, left_value) return righ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정 현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 후 탐색 범위를 좁히기 절단기의 높이는 0~10억까지 정수 중 하나 큰 범위는 대부분 이진 탐색 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 나올 동안 중간점의 값을 기록한다. [Step 1] 시작점: 0, 끝점: 19, 중간점: 9(자르고자 하는 높이) 이때 필요한 떡의 크기: M = 6이므로, 결과 저장 탐색 범위는 0~19이다 중간점은 나누면 9가 될 것이다. 잘린 떡의 길이는 모두 25가 나온다. 중간점의 9를 기록하고 중간점을 오른쪽으로 높이면서 또 확인한다. [Step 2] 시작점: 10, 끝점: 19,..

1. 새로 알게된 것 (파이썬 이진 탐색 라이브러리) bisect_left(a, x) 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 bisect_right(a, x) 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환 a라는 배열에 4가 있는 인덱스의 바로 왼쪽 a라는 배열에 4가 있는 인덱스의 바로 오른쪽 from bisect import bisect_left, bisect_right a = [1,2,4,4,8] x = 4 print(bisect_left(a,x)) print(bisect_right(a,x)) #출력 결과 2 4 2. 값이 특정 범위에 속하는 데이터 개수 구하기 from bisect import bisect_left, bisect_rig..

1. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 2. 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 3. 이진 탐색 동장 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시 [Step 1] 인덱스 시작점 : 0, 끝점 : 9, 중간점 : 4 중간지점은 인덱스 4.5인데 소수점 이하는 제거하므로 4즉, 인덱스 4번째를 중간점으로 선택 중간점과 찾고자하는 값(4)를 비교한다. 오른쪽은 필요가 없을 것이다. [Step 2] 시작점: 0, 끝점: 3, 중간점: 1 끝점은 중간점 바로 앞으로 바뀌고 다시 시작한다. 중간점이 찾고자 하는쪽의 오른쪽에 있..