코딩테스트 공부 (12) 썸네일형 리스트형 [백준 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 다음
