본문 바로가기

이진탐색4

#09 이진 탐색 정렬된 리스트에서 특정 값을 탐색할 때 순차 탐색보다 빠르게 탐색할 수 있는 알고리즘 순차 탐색 : O(n) 이진 탐색 : O(logn) ''' 1. start가 end보다 크다면 stop 2. mid 값을 정함 3. mid 인덱스의 값과 target이 같으면 return 4. mid 인덱스의 값보다 target이 작으면 mid 왼쪽에 있으므로 end 값을 mid -1 5. mid 인덱스의 값보다 target이 크면 mid 오른쪽에 있으므로 start 값을 mid + 1 ''' def binary_search(arr, start, end, target): if start > end: return None mid = (start + end)//2 if arr[mid] == target: return mid.. 2022. 1. 8.
[프로그래머스] 징검다리 건너기 (Python) https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 이진탐색으로 구현해야 풀리는 문제다 def step_stone(stones,num,k): cnt = 0 for stone in stones: if stone - num = k: return False return True def solution(stones, k): start = 1 end = 200000000 while (start 2021. 11. 16.
[프로그래머스] 금과 은 운반하기 (Python) https://programmers.co.kr/learn/courses/30/lessons/86053 코딩테스트 연습 - 금과 은 운반하기 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는 programmers.co.kr 이진 탐색으로 풀면 된다. 나의 풀이 def solution(a, b, g, s, w, t): start = 0 end = int(1e9*1e5*2*2) answer = end while start= a and all_silver >= b and all_total >= a+b : # 시간 더 줄이기 answer = min(answer,mid.. 2021. 11. 10.
#5 Python 코딩테스트 이진 탐색 https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5 이 포스팅은 위의 영상을 보고 제가 필요하다고 생각되는 부분을 정리한 포스팅입니다. 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다. 절반씩 데이터를 쪼개서 탐색하기 때문에 O(logN)의 시간 복잡도를 가지게 됨 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search_recursive(array, target.. 2021. 10. 20.

티스토리툴바