Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- input()
- 불리안
- false
- insert()
- 1일차
- 변수와 입출력
- a=1
- 변수
- 변할 수 있는
- 파이썬
- 그룹 # 그룹 해체 # 단축키 #figma #Figma
- 귀도 반 로섬
- 합집합
- 딥러닝
- null # undefined
- 성적 입력받기
- Python
- html
- 차집합
- index()
- append()
- 리스트와 차이점
- 정보를 담을 수 있는 그릇
- del()
- 조건문 큰 수부터 입력받아야하는 이유
- 부스트캠프
- pop()
- Java Script # == # === # difference # 차이
- 입출력
- 조지 불
Archives
- Today
- Total
I about me
[이것이 코딩테스트다] 5. 이진 탐색 본문
해당 강의를 참고하여 공부를 진행했습니다.
https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
이진 탐색 동작 예시
- 정렬된 데이터 중에서 특정 원소를 찾는 과정
- 시작점, 끝점, 중간점: 4 (소수점 이하 제거)
- 시간복잡도 O(log N)
- ex)
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if array[mid] == target:
return mid # 인덱스 값
elif array[mid] > target:
return binary_search(array, target, start, mid-1)
else:
return binary_search(array, target, mid+1, end)
# target : 찾고자 하는 값
n, target = list(map(int, input().split())) # 10, 7
array = list(map(int, input().split())) # 1 3 5 !!7!! 9 11 13 15 17 19
result = binary_search(array, target, 0, n - 1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result + 1) # 인덱스는 3이지만 4번째 원소이므로 결과값 4가 나옴
이진 탐색 라이브러리
- bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스
- bisect_right(a, x) 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 5, 8]
print(bisect_left(a, 3)) # [1, 2, 3, 4, 5, 8]
print(bisect_right(a, 6)) # [1, 2, 3, 4, 5, 6, 8]
print(a) # 적용이 안 됨
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))
응용
- 값이 특정 범위에 속하는 데이터 갯수
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
left_index = bisect_left(a, left_value)
right_index = bisect_right(a, right_value)
return right_index - left_index
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
print(count_by_range(a, 3, 3)) # 4
# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3)) # 6
파라메트릭 서치
- 파라메트릭 서치란 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법
- ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
- 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다
<문제>
떡복이 떡 만들기
n, m = list(map(int, input().split()))
array = list(map(int, input().split()))
start = 0
end = max(array)
result = 0
while(start <= end):
total = 0 # 떡의 양
mid = (start + end) // 2
for x in array:
if x > mid:
total += x - mid
if total < m:
end = mid - 1
else:
result = mid
start = mid + 1
print(result)
정렬된 배열에서 특정 수의 개수 구하기
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
left_index = bisect_left(a, left_value)
right_index = bisect_right(a, right_value)
return right_index - left_index
n, x = list(map(int, input().split())) # 7 2
array = list(map(int, input().split())) # 1 1 2 2 2 2 3
# print(count_by_range(array, x, x)) # 4
count = count_by_range(array, x, x)
if count == 0:
print(-1)
else:
print(count)
'Algorithm > 이것이 코딩테스트다!' 카테고리의 다른 글
[이것이 코딩테스트다] 7. 최단 경로 문제 (0) | 2024.07.25 |
---|---|
[이것이 코딩테스트다] 6. DP (1) | 2024.07.24 |
[이것이 코딩테스트다] 4. 정렬 (0) | 2024.07.19 |
[이것이 코딩테스트다] 3. DFS/ BFS (0) | 2024.07.18 |
[이것이 코딩테스트다] 2. 그리디 & 구현 (1) | 2024.07.18 |