Algorithm/Binary Search

Algorithm/Binary Search
[카카오코테] 가사 검색
문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다. 그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다. 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 qu..
→2021.02.09
Algorithm/Binary Search
[백준 2110] 공유기 설치
문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..
→2021.02.07
Algorithm/Binary Search
[Amazon 인터뷰] 고정점 찾기
초기접근 이진 탐색으로 data[mid] == mid 인지 확인해서 왼쪽, 오른쪽으로 나누려고 시도. 그런데 왼쪽, 오른쪽 나누는 기준을 모르겠음. 어떨때 왼쪽? 어떨때 오른쪽? data[mid-1] mid + 1 이면 오른쪽 으로 나눴음 그랬더니 mid가 0일때 무한루프에 빠짐. 반복문으로 이진탐색을 구현할때 내가 실수했던 점 while start mid 이면 오른쪽으로 풀면 끝 정답 코드 n = int(input()) data = list(map(int, input().split())) start = 0 end = n-1 result = -1 while start mid: end = mid-1 else: start = mid+1 print(resu..
→2021.02.06
Algorithm/Binary Search
[Zoho 인터뷰] 특정 원소 개수 찾기
풀이 python의 bisect를 이용하면 1분만에 풀 수 있지만, 이진탐색의 이해를 위해 이진탐색 메소드를 직접 구현해서 풀었다. bisect 이용 풀이 from bisect import bisect_left, bisect_right n, x = map(int, input().split()) arr = list(map(int, input().split())) left = bisect_left(arr, x) right = bisect_right(arr, x) result = right - left if result == 0: print("-1") else: print(result) 이진탐색 메소드 직접 구현 풀이 def first(data, target, start, end): if start > end..
→2021.02.05
Algorithm/Binary Search
이진탐색 이론
이진탐색은 이미 정렬되어 있는 데이터에서 절반씩 좁혀가며 탐색하는 방법 "이미 정렬", "절반씩" 0~10억 같은 큰 탐색범위를 보면 가장 먼저 이진탐색을 떠올려라 python에서 이진탐색 구현 def binary_search(data, target, start, end): if start > end: return None mid = (start+end) // 2 if data[mid] == target: return mid elif data[mid] > target: return binary_search(data, target, start, mid-1) else: return binary_search(data, target, mid+1, end) n, target = list(map(int, input..
→2021.02.05

• 이전
• 1
• 다음