기록일지

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.netN개의 집의 개수에 c개의 공유기를 설치하는데 공유기간 거리를 최대로 하고싶을때 공유기간 거리중 최소치를 구하시오. import sysinput = sys.stdin.readlinen,c =map(int,input().split())arr = []for _ in range(n): arr.append(int(input()))arr.sort()def..

코딩테스트/이진 탐색 2024. 9. 11. 12:04

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제요약: 숫자리스트 들이 주어질때 두 숫자를 합한값이 해서 0에 가장 가까운 두 숫자를 오름차순으로 출력하라 난이도: 골드5 소요시간: 30분 제출횟수: 매우많음 코딩: import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) arr = list(map(int,inp..

코딩테스트/이진 탐색 2023. 10. 17. 16:52

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제요약: 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 난이도: 골드4 소요시간: 10분 제출횟수: 1회 코딩: import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) arr = list(map(int,input().split())) ans1..

코딩테스트/이진 탐색 2023. 10. 7. 16:56

https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명: 돌의 내구도 가 주어지고 한번에 건널수 있는 최대값이 주어진다. 최대 몇명이 건너갈 수 있는가 소요시간: 50분 난이도 3 1차 코딩: (15분) def solution(stones, k): q = [] for i in range(len(stones)-k+1): q.append(max(stones[i:i+k])) return min(q) 저는 이문제의 대한 알고리즘을 주어진 구간의 대해..

코딩테스트/이진 탐색 2023. 7. 5. 14:15

이진정렬 문제를 풀때, underbounded , upperbounded에 대한 개념이 명확하지 않아, 관련문제가 자꾸 헷갈려 직접 구현하며 개념을 정리하려 합니다. bisect_left arr = list(map(int,input().split())) def bisect_left(k): lo = 0 hi = len(arr)-1 while lo

코딩테스트/이진 탐색 2023. 6. 7. 19:59

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 요약: 숫자 배열이 주어지고 특정 수보다 큰 수들과의 차이의 합이 정해진 m보다 커지는 수중 가장 큰수를 구하여라 실버2 소요시간: ~ 1차 접근 : 먼저 m의 범위를 보고 2진탐색을 해야겠다고 생각한 뒤, 중간값을 정하고 이진탐색을 진행했다. from bisect import bisect_left import sys input = sys.stdin.r..

코딩테스트/이진 탐색 2023. 6. 2. 10:36