본문 바로가기

이분탐색13

[백준] 24041번 - 성싶당 밀키트 (파이썬) # 성싶당 밀키트 import sys from collections import defaultdict input = sys.stdin.readline N, G, K = map(int, input().split()) info = defaultdict(list) for _ in range(N): speed, limit, isImportant = map(int, input().split()) info[isImportant].append((speed, limit)) def get_g(x, k): result = 0 for speed, limit in info[0]: result += speed*max(1, x-limit) info[1].sort(key=lambda k: -k[0]*max(1, x-k[1])) f.. 2022. 4. 15.
[백준] 9007번 - 카누 선수 (파이썬) # 카누 선수 import sys input = sys.stdin.readline T = int(input()) for _ in range(T): k, n = map(int, input().split()) arr = [] for _ in range(4): arr.append(list(map(int, input().split()))) one, two = set(), set() for idx in range(0, 4, 2): for x in arr[idx]: for y in arr[idx+1]: one.add(x+y) if idx == 0 else two.add(x+y) one = sorted(list(one)) two = sorted(list(two)) # 투포인터 result = 0 diff = sys... 2022. 4. 8.
[백준] 3151번 - 합이 0 (파이썬) # 합이 0 from bisect import bisect_left N = int(input()) arr = list(map(int, input().split())) arr.sort() answer = 0 for i in range(len(arr)-2): left, right = i+1, N-1 while left 0: right -= 1 else: if result == 0: if arr[left] == arr[right]: answer += right - left else: idx = bisect_left(arr, arr[right]) answer += right-idx+1 left += 1 pri.. 2022. 4. 8.
[백준] 17951번 - 흩날리는 시험지 속에서 내 평점이 느껴진거야 (파이썬) # 흩날리는 시험지 속에서 내 평점이 느껴진거야 N, K = map(int, input().split()) arr = list(map(int, input().split())) answer = 0 left, right = 0, int(1e5)*20+1 while left = mid: group += 1 score = 0 # 다음 if group >= K: answer = mid left = mid+1 else: right = mid-1 print(answer) 이분탐색 1. 입력을 받는다. 출력은 최대 점수 (left와 right을 얻을 수 있는 점수로 설정) 2. left = 0, right = 최대 시험 점수 + 1 (N은 최대 10^5개, 각 점수는 최대 20점) 3. 이분탐색 - 점수가 mid 일 .. 2022. 4. 6.
[백준] 1365번 - 꼬인 전깃줄 (파이썬) # 꼬인 전깃줄 import bisect N = int(input()) arr = list(map(int, input().split())) result = [arr[0]] for i in range(1, len(arr)): index = bisect.bisect_left(result, arr[i]) if index == len(result): result.append(arr[i]) else: result[index] = arr[i] print(len(arr)-len(result)) 이분탐색, bisect 1. 입력을 받는다. 2. result 리스트 선언 3. arr의 각 원소마다 - result가 비었으면 append - bisect_left로 result에 x가 들어갈 인덱스를 구한다. - index.. 2022. 4. 5.
[프로그래머스] Lv2 - 순위 검색 (파이썬) https://programmers.co.kr/learn/courses/30/lessons/72412 = score: right = mid else: left = mid + 1 answer.append(len(arr)-left) 2021 카카오 블라인드, 이분탐색, 해시 1. dict = 각 키마다 점수를 저장해 줄 defaultdict(list) 2. info리스트 내부의 값마다 (점수를 제외한 값을 key, 점수를 score) - add : key의 리스트 값 중 0부터 4개를 가지는 모든 값(조합)을 문자열로 변환, 해당 값의 dict에 score 추가 3. 모든 키의 값(점수가 들어있는 리스트)들을 정렬 4. query리스트의 모든 값마다 'and'와 '-'를 삭제해주고 split() (점수를 제.. 2022. 4. 5.
[백준] 2866번 - 문자열 잘라내기 (파이썬) # 문자열 잘라내기 from collections import defaultdict R, C = map(int, input().split()) arr = [list(input()) for _ in range(R)] result = 0 start, end = 0, R-1 while start 2022. 4. 4.

티스토리툴바