알고리즘/자료구조(44)
-
백준 온라인 저널, 우선순위 큐, 자료구조/1927번 : 최소 힙(파이썬) /11279번 : 최대 힙(파이썬)
최소 힙 문제 정의 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 ..
2021.06.24 -
우선순위 큐 개념 정리(리스트 우선순위큐, 힙 우선순위큐 / 시간복잡도 / 파이썬 구현)
우선순위 큐 특징 : 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예시) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 구현 방법 1) 단순히 리스트를 이용하여 구현한다. 2) 힙(heap)을 이용하여 구현한다. 시간복잡도 - 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같다. 1) 리스트 - 삽입 시간 : O(1) (리스트의 가장 뒤에 추가가 되기에 O(1)이 소요됨) - 삭제 시간 : O(N) (모든 데이터를 확인하기 때문에 선형 시간 복잡도를 가짐) 2) 힙 - 삽입 시간 : O(logN) - 삭제 시간 : O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙정..
2021.06.18