분류 전체보기 (17) 썸네일형 리스트형 [백준 1051 파이썬] 처음에 내가 푼 방법 : import sys n,m = map(int,sys.stdin.readline().split()) data=[input() for _ in range(n)] result =[1] for k in range(1,min(n,m)): for i in range(n): for j in range(m): if i+k [백준 11286 파이썬] 절대힙을 구현하는 문제이다. 파이썬의 heapq를 import해서 구현했다. 최소힙을 구현하는 방식과 같지만 heapq.heappush를 할 때 abs(value)와 value를 튜플 형태로 넣어준다. 시간 초과가 뜬다면 input() 대신 sys를 import 하고 sys.stdin.readline() 를 쓰면된다. import heapq,sys min_heap=[] n=int(input()) data=[int(sys.stdin.readline()) for _ in range(n)] abs_heap=[] for value in data: if value ==0 : if abs_heap==[] : print(0) else: print(heapq.heappop(abs_heap)[1]) else : heap.. [백준 11279 파이썬] 최대힙을 구현하는 문제이다. 파이썬의 heapq를 import해서 구현했다. 최소힙을 구현하는 방식과 같지만 heapq.heappush를 할 때 -부호를 붙혀주고 출력할 때도 -를 붙혀주면 된다. 시간 초과가 뜬다면 input() 대신 sys를 import 하고 sys.stdin.readline() 를 쓰면된다. import heapq n=int(input()) data=[int(input()) for _ in range(n)] max_heap=[] for value in data: if value ==0 : if max_heap==[] : print(0) else: print(-(heapq.heappop(max_heap))) else : heapq.heappush(max_heap,-value) [백준 1927 파이썬] 최소힙을 구현하는 문제이다. 파이썬의 heapq를 import해서 구현했다. 시간 초과가 뜬다면 input() 대신 sys를 import 하고 sys.stdin.readline() 를 쓰면된다. #1927 import heapq min_heap=[] n=int(input()) data=[int(input()) for _ in range(n)] min_heap=[] for value in data: if value ==0 : if min_heap==[] : print(0) else: print(heapq.heappop(min_heap)) else : heapq.heappush(min_heap,value) [백준 11000 파이썬] 우선 순위 큐를 이용하는 문제이다. list로 구현을 하게 되면 시간초과가 된다. 따라서 파이썬에서 heap 모듈을 import해서 구현했다. #11000 n=int(input()) data=[list(map(int,input().split())) for _ in range(n)] data.sort() room=[] room.append(data[0][1]) ''' 이렇게 하면 시간초과 for i in range(1,len(data)): print(room) if data[i][0] 코딩테스트 알고리즘 종류 [문제유형] 그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 구현 완전탐색 : 모든 경우의 수를 주저없이 다 계산 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행 DFS/BFS [복잡도] 1.시간 : 연산 횟수 1초에 2000만 번~ 1억 번 정도의 연산 처리 가능 ex) N= 1000000 -> O(NlogN) = 2000만 번 공간 : 메모리 양 [백준 1715 파이썬] 1. data중에서 가장 작은 값 2개를 뽑아서 연산을 해주고 2. 그 결과를 다시 data에 넣어준다. 1,2번 방법을 반복하는데 data의 갯수가 1개일 때 결과를 반환하면 된다. iterable한 data에서 계속해서 가장 작은 값을 뽑아야함으로 우선 순위 큐(Priority queue) 자료구조를 이용해서 풀어야한다. 우선 순위 자료 구조를 구현하기 위해선 파이썬의 heapq 모듈을 이용할 수 있다. import heapq n=int(input()) data=[int(input()) for _ in range(n)] heapq.heapify(data) result =0 while len(data) >1 : min = heapq.heappop(data) min_2 = heapq.heappop(dat.. [자료구조]우선순위 큐(Priority Queue)와 힙(Heap) 백준 1715번 문제를 풀다가 "우선 순위 큐(Priority Queue)"에 대해 알게 되었고 우선순위 큐를 구현하기 위해 파이썬의 heapq 모듈 사용 중 heapq.heappush 하는 과정이 이해가 가지 않아서 이를 계기로 '나동빈'님의 영상을 보게 되었습니다. import heapq #heap 라이브러리 importheap_list = []iterable =[3,5,9,6,4] for value in iterable : heapq.heappush(heap_list,value) #heap 라이브러리의 heappush 함수를 이용해서 iterable의 원소를 heap_list에 추가 print(heap_list) 위의 코드는 파이썬에서 heap 라이브러리를 import하고 heapq.heappu.. 이전 1 2 3 다음
