https://www.acmicpc.net/problem/1927
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
https://www.acmicpc.net/problem/11279
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
solve.ac에 있는 Class 3의 문제를 푸는데 마침 두 문제를 동시 풀 수 있는 개꿀따리가 나타났다.
2학년 자료구조 시간에 heap 이라는 자료구조를 배웠었다. 이 구조를 이용하여 문제를 푸는 것이다.
파이썬의 엄청난 기능을 활용할 수 있는 때는 지금과 같은 상황이다.
원래는 Tree 구조로 해서 직접 heap 구조를 만들어야 한다.
하지만, 파이썬은....
이걸로 모든게 끝이다.
하나의 리스트를 만든 뒤, heappush 및 heappop 연산을 해주면 알아서 heap 구조를 유지시키면서 원활한 연산을 해줌과 동시에 시간복잡도 마저도 효율적이게 해준다.
heappush같은 경우 O(log n), heappop은 O(1)로 두게끔 해준다.
but, 최소 힙 문제는 아무래도 입력하고자 하는 값들이 많기 때문에 import sys를 통해 sys.stdin.readline() 입력을 받게끔 해야했다.
그래야 성공할 수 있었다.
다음으로는, 최대힙 문제이다.
이전의 최소힙과 차이점은 원래 heapify()(?)라는 것을 통해 최소 힙을 나열해보면 오름차순으로 구조가 이루어짐을 알 수 있다.
하지만, 최대힙은 내림차순 이라는 것이다.
그러면 기존의 heap 자료구조를 어떻게 이용하면 될까?
heappush의 연산자는 항상 첫번째 입력값에 대해 들어가고자 하는 heap의 위치에 들어가게되는데 이를 이용할 수 있다.
heappush의 입력을 n을 받아야할때, tuple 형식으로 -n, n을 받는 것이다.
그러면 heappop을 할때 0번째가 아닌 1번째 인덱스를 출력하게 하면 내림차순으로 출력되는 것을 확인할 수 있다.
tuple 형식도 입력으로 사용할 수 있다는 것을 이용하여 최대힙을 손쉽게 구현할 수 있었다.
1일 1백준 22일째...
'백준에 대가리 깨지는중' 카테고리의 다른 글
[백준] 실버1 쿼드트리 (0) | 2023.05.30 |
---|---|
[백준] 골드4 이중 우선순위 큐 (2) | 2023.05.30 |
[백준] 골드5 5430 AC (0) | 2023.05.28 |
[백준] 골드5 10026 적록색약 (0) | 2023.05.27 |
[백준] 실버3 9375 패션왕 신해빈 (0) | 2023.05.27 |