본문 바로가기

이진탐색7

[프로그래머스] 고득점Kit (9) - 이분탐색 (파이썬) 1. 입국심사 (Lv. 3) # 입국심사 def solution(n, times): answer = 0 times.sort() left, right = 1, max(times)*n while left = n: answer = mid right = mid - 1 elif temp < n: left = mid + 1 return answer right = max(times)*n : 가장 긴시간으로 n명이 입국심사를 했을 때가 최댓값 이분탐색 실시 - mid : 걸린 총 시간 - temp : 해당 시간 안에 입국 심사를 할 수 있는 사람의 수 - temp == n 을 목표로 이분탐색을 진행 2. 징검다리 (Lv. 4) # 징검다리 def solution(distance, rocks, n): answer = 0.. 2022. 3. 12.
[백준] 2143번 - 두 배열의 합 (파이썬) # 두 배열의 합 import sys import bisect input = sys.stdin.readline K = int(input()) N = int(input()) A = list(map(int, input().split())) M = int(input()) B = list(map(int, input().split())) sum_A = [] for i in range(N): sum = 0 for j in range(i, N): sum += A[j] sum_A.append(sum) sum_B = [] for i in range(M): sum = 0 for j in range(i, M): sum += B[j] sum_B.append(sum) result = 0 sum_B.sort() for sum_a.. 2022. 2. 18.
[백준] 2352번 - 반도체 설계 (파이썬) # 반도체 설계 import sys import bisect input = sys.stdin.readline N = int(input()) port = list(map(int, input().split())) result = [port[0]] for x in range(1, N): if port[x] > result[-1]: result.append(port[x]) else: index = bisect.bisect_left(result, port[x]) result[index] = port[x] print(len(result)) 이진탐색, bisec 1. 입력을 받고 port의 첫번째 값을 result에 추가 2. 남은 port의 값중에서 - result의 마지막 값보다 크면 append - result.. 2022. 2. 18.
[백준] 12738번 - 가장 긴 증가하는 부분 수열 3 (파이썬) # 가장 긴 증가하는 부분 수열 3 import sys import bisect input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) result = [arr[0]] for i in range(1, N): if arr[i] > result[-1]: result.append(arr[i]) else: index = bisect.bisect_left(result, arr[i]) result[index] = arr[i] print(len(result)) 이진탐색, bisect 1. 전체 리스트를 돌면서 - result의 마지막 원소보다 크면 append를 해준다 - 작으면 bisect_left를 이용하여 해당 인덱스의 .. 2022. 2. 7.
[백준] 7453번 - 합이 0인 네 정수 (파이썬) # 합이 0인 네 정수 import sys input = sys.stdin.readline N = int(input()) A, B, C, D = [], [], [], [] for _ in range(N): a, b, c, d = map(int, input().split()) A.append(a) B.append(b) C.append(c) D.append(d) AandB = [] for a in A: for b in B: AandB.append(a+b) AandB.sort() CandD = [] for c in C: for d in D: CandD.append(c+d) CandD.sort() result = 0 left, right = 0, len(CandD)-1 sum = 0 while 0 0: righ.. 2022. 2. 5.
[백준] 1300번 - K번째 수 (파이썬) # K번째 수 N = int(input()) k = int(input()) start, end = 1, k result = 0 while start = k: result = mid end = mid - 1 else: start = mid + 1 print(result) 이진탐색 B리스트는 정렬된 상태라고 문제에 적혀져있다. 이분탐색을 사용 B[k]는 항상 k보다 작거나 같기 때문에 end를 k로 지정해준다. 1. start가 end보다 작거나 같을 동안 이진 탐색 수행 - count : mid보다 작은 수들의 개수 - 해당 열에서 X보다 작은 수의 개수는 X를 해당 열의개수(1~N)으로 나눈값 (단, N보다 커질 수 없음) 2. count == k 이면 result를 출력 아 좀 많이 해맸다... 이진탐.. 2022. 1. 31.
[백준] 12015번 - 가장 긴 증가하는 부분 수열 2 (파이썬) # 가장 긴 증가하는 부분 수열 2 import sys import bisect input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) result = [] result.append(arr[0]) for i in range(1, N): if arr[i] > result[-1]: result.append(arr[i]) else: index = bisect.bisect_left(result, arr[i]) result[index] = arr[i] print(len(result)) 이진탐색, bisect 1. 전체 리스트를 돌면서 - result의 마지막 원소보다 크면 append를 해준다 - 작으면 bisect_lef.. 2022. 1. 27.

티스토리툴바