이진 탐색
탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 O(logN)
- 전제 조건 : 데이터가 '정렬' 되어 있어야 함
- Tree 자료구조로 데이터를 저장하면 이진 탐색과 같은 기법으로 빠르게 탐색이 가능
재귀함수로 구현
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)
반복문으로 구현
def binary_search(array, target, start, end):
while start <= end:
mid = (start+mid) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
(내가 생각하는) 좋은 문제
2295번: 세 수의 합
우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최
www.acmicpc.net
2512번: 예산
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상
www.acmicpc.net
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
1939번: 중량제한
첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이
www.acmicpc.net
1561번: 놀이 공원
첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30
www.acmicpc.net
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 백준 14501 - 퇴사 파이썬 (0) | 2023.03.28 |
|---|---|
| 백준 9465 - 스티커 파이썬 (0) | 2023.03.27 |
| 프로그래머스 - 크레인인형뽑기게임 파이썬 (0) | 2023.03.20 |
| 프로그래머스 - 명예의 전당(1) 파이썬 (0) | 2023.03.14 |
| 백준 3040 - 백설공주와 일곱 난쟁이 파이썬 (0) | 2023.03.13 |
댓글