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

[Python]우선순위큐 백준 1655

문제 https://www.acmicpc.net/problem/1655 넣을때마다 정렬해주는 방법과 최대힙과 최소힙을 이용하여 중간값을 찾는 방법이있다.두 방법다 가능해보이지만 첫번째 방법은 넣을때마다 한칸씩 밀리거나 댕겨야 하는 상황이 나올수 있기 때문에 그 시간이 오래걸린다.두번째 방법으로 구현해 보았다.힙은 heapq모델을 사용하였다. 힙두개를 작성하여 사용하기에는 너무 코드가 길어진다. 1234567891011121314151617181920212223import sysimport heapq#heapq는 최소힙만 지원한다 최대힙을 구현하기위해선 -를 곱해서 넣어 주고 꺼낼때 다시 -를 곱해준다 def middleheap(minheap,maxheap,x):#넣기만함 if len(maxheap)==l..

2020. 2. 2. 14:15
알고리즘(python)/자료구조

[Python]우선순위큐 백준 11286

문제 https://www.acmicpc.net/problem/11286 전체적인 구현은 앞의 우선순위큐와 거의 동일하다.절대값으로 변환하여 비교해주고 절대값이 같을때 작은경우가 부모노드가 될수있도록 하면된다.절대값은 직접 구현할수도 있지만 너무 지저분해질거 같아서 abs()함수를 사용하여 비교하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465import sysinput=sys.stdin.readlinepq=[]pqlen=0#길이 N=int(input())while N>0: N-=1 x=int(input()) if x!=0:#pus..

2020. 2. 2. 09:09
알고리즘(python)/자료구조

[Python]우선순위큐 백준 1927

문제 https://www.acmicpc.net/problem/1927 잘려고 하다가 최대힙에서 부호만 바꾸어주면 되는거 같아서 이렇게 작성하고 잔다.스왑하는 부분만 부호를 바꾸어주면된다. 1234567891011121314151617181920212223242526272829303132333435363738394041import sysinput=sys.stdin.readlinepq=[]pqlen=0#길이 N=int(input())while N>0: N-=1 x=int(input()) if x>0:#push pq.append(x) #제일끝에 추가해준다 pqlen += 1 a=pqlen-1 while a>0:#힙구조 만들기 if pq[a]

2020. 2. 2. 00:26
알고리즘(python)/자료구조

[Python]우선순위큐 백준 11279

문제 https://www.acmicpc.net/problem/11279 앞서 힙정렬을 구현할때 사용하였으므로 따로 설명을 붙이지는 않겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142import sysinput=sys.stdin.readlinepq=[]pqlen=0#길이 N=int(input())while N>0: N-=1 x=int(input()) if x>0:#push pq.append(x) #제일끝에 추가해준다 pqlen += 1 a=pqlen-1 while a>0:#힙구조 만들기 if pq[a]>pq[(a-1)//2]: #부모보다 크다면 바꾸어준다 끝까지 도달하거나 바꿀필요가 없을때까지 pq[a],pq[(..

2020. 2. 1. 23:44
알고리즘(python)/탐색

[Python]이분탐색 백준 12015

문제 https://www.acmicpc.net/problem/12015 이전에 봤던 문제이다.동적계획법에서 봤던 문제이고 조금 고생했던것도 기억이난다.그때 마음에 걸렸던 시간복잡도O(N^2)인 것도 생각이 나는데 이번에는 이분탐색을 통해 해결할수 있는것인지 이분탐색 문제에서 N의 크기를 100만으로 키워 다시나왔다.굉장히 보기쉽게 잘 나와있다.https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4 코드는 이전과 크게 다르지 않다. 12345678910111213141516171819202122232425262728import sys N=int(sys.stdin.readline(..

2020. 2. 1. 16:28
알고리즘(python)/탐색

[Python]이분탐색 백준 1300

문제 https://www.acmicpc.net/problem/1300 http://wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/설명이 가장 잘되어있는거같다.위 설명대로 했을때 의심되는부분만 다시 짚어보았다.초기값 설정문제 right를 N^2을 해야 맞지않는가이부분은 숫자를 나열해봐도 알수있다. k번째 숫자는 절대 k보다 클수가 없다.ans값이 배열에 없다면?우리는 만족하는 값중에 가장 작은값을 찾는다. 그렇다면 그 바뀌는 경계선에서는 그 숫자가 존재하기 때문에 바뀌는것이다.아래 가져온 설명과 같이 만족하는 최솟값을 찾는다면 그수는 포함할수 밖에 없다. 아래 설명을 참고했다.https://www.acmicpc.net/board/view/..

2020. 2. 1. 13:15