본문 바로가기

이분탐색

 (13)
[이분탐색] 백준 2110번 '공유기 설치' (Python) https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 처음 최소 거리는 항상 1, 최대 거리는 max-min 2. mid 거리만큼 차례대로 공유기를 설치함. (집이 1,4,8,9이고, mid가 4일 때, 1,8에 공유기 설치 가능) 3. 2개밖에 설치 못하므로 거리-1, 그 반대면 +1 #이취코 답 n,c = list(map(int,input().split())) array = [] for _..
[이분탐색] 릿코드 153 Medium 'Find Minimum in Rotated Sorted Array' (Python) https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Find Minimum in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 배열의 최소 요소를 반환하라고 했으므로 min 함수 사용 class Solution: def findMin(self, nums: List[int]) -> int: return min(nums)
[이분탐색] 릿코드 Medium 74 'Search a 2D Matrix' (Python) https://leetcode.com/problems/search-a-2d-matrix/ Search a 2D Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 각 행에 target 값이 있으면 true class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for i in matrix: if target in i: return True retur..
[이분탐색] 릿코드 Medium 33 'Search in Rotated Sorted Array' (Python) https://leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. nums에서 target의 인덱스 값을 찾아라 2. target 값이 없으면 -1 class Solution: def search(self, nums: List[int], target: int) -> int: if target in nums: ..
[이분탐색] 릿코드 Easy 35 'Search Insert Position' (Python) https://leetcode.com/problems/search-insert-position/ Search Insert Position - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 정렬된 배열에 값을 넣으면 그 값에 대한 인덱스를 찾아주는 파이썬 라이브러리 사용 from bisect import bisect_left class Solution: def searchInsert(self, nums: List[int], target: int) -> int..
[이분탐색] 릿코드 Easy 278 'First Bad Version' (Python) https://leetcode.com/problems/first-bad-version/ First Bad Version - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 원소의 값이 크기 때문에 이분 탐색으로 정답을 찾아야 함 # The isBadVersion API is already defined for you. # @param version, an integer # @return an integer # def isBadVersion(version): cla..
[이분탐색] 릿코드 Easy 704 'Binary Search' (Python) https://leetcode.com/problems/binary-search/ Binary Search - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이분탐색으로 리스트의 인덱스 찾기 class Solution: def search(self, nums: List[int], target: int) -> int: def binary_search(array,target,start,end): if start>end: return None mid = (start+e..
[이분탐색] 난이도2, Zoho 인터뷰 '정렬된 배열에서 특정 수의 개수 구하기' (Python) N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1
LIST

티스토리툴바