결정알고리즘 (4) 썸네일형 리스트형 [python] 코딩테스트 대비 - 이분검색(일직선에 배치) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import sys #sys.stdin=open("input.txt", "r") def Count(len):#len으로 배치 할 수 있는 마리수 리턴 cnt=1#마리 수 ep=Line[0]#최근에 말을 배치한 우;ㅊ; for i in range(1, n): if Line[i]-ep>=len:#배치 할 수 있다면, cnt+=1 #마리수 증가 ep=Line[i] #끝지점 변경 return cnt n, c=map(int, input().split()) Line=[] for _ in range(n): tmp=int(input()) Line.appen.. [python] 코딩테스트 대비 - 이분검색(최소 길이 구하기) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import sys #sys.stdin=open("input.txt", "r") def Count(capacity):#해당 용량으로 만들 수 있는 dvd 갯수 리턴 cnt=1 sum=0 for x in Music: if sum+x>capacity: cnt+=1 sum=x else: sum+=x return cnt n, m=map(int, input().split()) Music=list(map(int, input().split())) maxx=max(Music)#음악 중 최고 용량 lt=1 rt=sum(Music)#1개 dvd에 모든 노래를 .. [python] 코딩테스트 대비 - 이분검색(랜선자르기) 문제) 답안 코드) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sys #sys.stdin=open("input.txt", "r") def Count(len):#len으로 짜를 수 있는 총 갯수 리턴 cnt=0 for x in Line: cnt+=(x//len) return cnt k, n=map(int, input().split()) Line=[]#길이 리스트 res=0#정답 largest=0#최대 값 for i in range(k): tmp=int(input()) Line.append(tmp) largest=max(largest, tmp) lt=1 rt=largest#1~최대값 범위 지정 whi.. [python] 코딩테스트 대비 - 이분검색(결정알고리즘) 문제) 답안 코드) 이분 탐색은 시간 복잡도 log_2 N을 보장한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys #sys.stdin=open("input.txt", "r") n, m=map(int, input().split()) a=list(map(int, input().split())) a.sort() lt=0#왼쪽 포인터 rt=n-1#오른쪽포인터 while ltm:#중간값이 정답보다 크다면, rt=mid-1 else:#작다면 lt=mid+1 cs 이전 1 다음
