30_가사 검색 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이진 탐 happenundo.tistory.com
이진탐색
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이진 탐색 문제. 아무리 생각해봐도 어떻게 이진 탐색을 돌아야 될지 모르겠어서 풀이를 봤다. 풀이 코드 # 가사 검색 from bisect import bisect_left, bisect_right # 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수 def count_by_range(arr, left_value, right_value): right_index = bisect_right(arr, right_value) left_index = bisect_left(arr, le..
29_공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ happenundo.tistory.com
2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제는 N개의 집 중에, C개의 공유기를 설치하는 문제다. 단, C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 해야 한다. 시간 제한이 2초이고, 집의 좌표는 최대 10억이다. 그러므로 O(N) 시간으로는 불가능할 것이고, O(logN) 시간으로 풀어야 하겠다는 생각이 들었다. 그렇다면 이진 탐색인데, 이진 탐색을 어떻게 돌아야 할까? 그래서 이렇게저렇게 생각을 ..
이진 탐색 문제다. 고정점이란, 수열의 원소중 그 값이 인덱스와 동일한 원소를 의미한다. 이 고정점을 찾는 코드를 구현하라. 단, 수열은 오름차순으로 주어지고, 시간복잡도는 O(logN)이다. 이진 탐색으로 구현하면 된다. 내 풀이 코드 # 고정점 찾기 def find_fix_point(array, start, end): if start > end: return None mid = (start + end) // 2 # 확인할 인덱스 if array[mid] == mid: return mid # 배열의 값이 0보다 작은 경우에는 그 왼쪽 값들은 볼 필요 없다. # 오른쪽 확인 if array[mid] < 0: return find_fix_point(array, mid + 1, end) # 확인할 인덱스의 ..
이 문제는 정렬된 배열에서 특정 수의 개수를 구하는 문제이다. 단 ,이 문제의 시간 복잡도는 O(logN)이다. O(N)이라면 그냥 for문을 돌면서 개수를 구하면 되지만, O(logN)이므로 이진탐색을 통해 구해야 한다. 다행히, 배열이 정렬되어 주어지므로, 따로 주어진 배열을 정렬할 필요 없이, 바로 이진탐색을 진행할 수 있다. 내 풀이 코드 # 정렬된 배열에서 특정 수의 개수 구하기 import sys from bisect import bisect_left, bisect_right input = sys.stdin.readline n, x = map(int, input().split()) arr = list(map(int, input().rstrip().split())) cnt = bisect_rig..
