알고리즘(python) 검색 결과
179 개의 검색 결과가 있습니다.
알고리즘(python)/탐색

[Python]이분탐색 백준 2110

문제https://www.acmicpc.net/problem/2110 두 공유기 사이의 거리를 기준으로 이분탐색을 시행한다.두공유기의 거리를 임의로 정하고 집의 좌표를 정렬한후 각 거리만큼 더해가며 집사이의 거리가 임의의 거리보다 크다면 공유기를 설치해준다.이렇게 설치를 하고 공유기의 설치수가 원하는 공유기의 개수보다 많거나 같다면 거리를늘려서 다시 탐색하고 공유기수가 작개 나온다면 거리를 줄여서 다시 계산한다. 처음 짠 코드가 오래걸려서 입출력을 바꾸었다. 123456789101112131415161718192021222324252627282930313233import sysinput=sys.stdin.readlineN,C=map(int,input().split())c_list=[]for i in ra..

2020. 2. 1. 11:39
알고리즘(python)/탐색

[Python]이분탐색 백준 2805

문제https://www.acmicpc.net/problem/2805 M의 나무를 가져가야 할때 최악의 상황에서 최대길이에 M만큼을 뺀 길이만큼 절단해야 한다.(높이는 최소)이값과 최대길이의 값의 중간값을 기준으로 이분탐색을 시행해 준다.코드로 구현해보자 12345678910111213141516171819202122232425import sys N,M=map(int,sys.stdin.readline().split())tree=list(map(int,sys.stdin.readline().split())) max_cut=max(tree)min_cut=max_cut-M#나무를 가장 많이 자를때 result=0while min_cutmid: sum_tree+=i-mid if sum_tree>=M:#원하는 목재..

2020. 1. 31. 21:52
알고리즘(python)/탐색

[Python]이분탐색 백준 1654

문제 https://www.acmicpc.net/problem/1654 길이를 기준으로 생각해야한다.길이에 따라 나오는 랜선의 갯수가 N보다 많은것중에 가장 긴것을 구하기 위해선 가능한 랜선의 범위를 정하고 이분탐색을 통해 그 범위를 좁혀나가면 된다.길이의 후보군은 1~가장긴랜선이 될것이다.그 중간값을 기준으로 랜선들을 잘랐을때 N개 이상의 랜선이 나온다면 랜선의 길이를 늘리고 N개가 나오지 않는다면 줄여야한다. 여기서 랜선의 길이를 이분법을 통해 늘리고줄여주면된다.코드를 보면 이해가 빠를것이다. 123456789101112131415161718192021222324import sysK,N=map(int,sys.stdin.readline().split())lanline=[]for i in range(K)..

2020. 1. 31. 19:40
알고리즘(python)/탐색

[Python]이분탐색 백준 10816

문제 https://www.acmicpc.net/problem/10816 가장먼저 생각해볼수잇는 카운팅정렬을 통해 구현할수 잇을거같다.메모리 제한에 걸리지 않는다. 1234567891011import sysN=int(sys.stdin.readline())card=[0 for _ in range(20000001)]N_list=list(map(int,sys.stdin.readline().split()))for i in N_list: card[i+10000000]+=1 M=int(sys.stdin.readline())M_list=list(map(int,sys.stdin.readline().split()))for i in M_list: print(card[i+10000000],end=" ")cs 이분탐색은 사용..

2020. 1. 31. 16:53
알고리즘(python)/탐색

[Python]이분탐색 백준 1920

문제https://www.acmicpc.net/problem/1920 가장기본적인 이분탐색이다.각단계마다 반씩 줄어들어서 logN만큼의 시간이 소요된다.A를 정렬하고 각 수가 주어질때마다 A의 중앙값보다 작다면 앞에서 크다면 뒤에서 다시 이분탐색을 시행한다. 1234567891011121314151617181920212223242526272829import sys def binary_search(start,end,M): if start>end: return 0 mid=(start+end)//2 if A[mid]==M:#같다면 서치종료 return 1 elif A[mid]>M:#M이 중앙값보다 작다면 앞에서 비교 return binary_search(start,mid-1,M) else:#크다면 뒤에서 비교..

2020. 1. 31. 13:45
알고리즘(python)/기본

[Python]분할정복 백준 2749

문제 https://www.acmicpc.net/problem/2749 n의 크기가 무지막지하다.주어진 n의 크기는 0의 숫자 조차 세기 힘들다.메모이제이션은 O(n)이라는 시간이 걸린다. 보통의 풀이방식으로는 불가능하다피보나치 수열을 분할정복으로 풀 수 있는 방법이 있다는건데 찾아봐야겟다...https://www.acmicpc.net/blog/view/28https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9..

2020. 1. 29. 22:48