파이썬 힙
-
[ Data Structure ] Heap 힙 & 우선순위 큐공부 !/Computer Science 2022. 4. 14. 23:44
Heap 힙은 어떤 자료구조인가 ! 비선형 자료구조의 일종으로 최소값과 최대값을 빠르게 찾기 위한 이진트리 구조이다 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다 힙은 heapq 내장 모듈로 구현할 수 있고 우선순위 큐는 힙으로 구현이 가능하다 ! 최소 힙은 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙을 의미하고 최대 힙은 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙을 의미한다 힙은 완전이진트리의 성질을 갖고 1차원 배열로 표현이 가능하다 아래를 참고하면 root index 에 따라 chlid index 를 계산할 수 있다 root index = 0 left index = index * 2 + 1 right index = index * 2 + 2 ..
-
[백준 11286] 절댓값 힙Algorithm/Source Code 2021. 11. 3. 00:00
문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. 출력 입력에서 0이 주어진 회수..
-
[프로그래머스 42626] 더 맵게Algorithm/Source Code 2021. 10. 25. 00:39
문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scovil..