본문 바로가기
반응형

힙

 (3)
[백준] 최대 힙(python) 백준, 최대 힙 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net TL;DR 우선순위 큐(Priority queue) 문제 요약 1. 입력받은 X가 자연수라면 배열에 넣고 0이라면 배열에 있는 값 중 가장 큰 값을 출력하고 값을 배열에서 제거한다. - 입력에 따라 수행되는 구문이 다르며, 0이 입력되었을 때 배열 내에서 가장 큰 수를 출력해야 한다. - 이를 완전 탐색으로 풀 때, 최악의 경우 O(n^2)가 되므로 다른 방법을 찾아야 한다. - 가장 큰 값에 우선순위를 두어 우선순위 큐를 사용..
[프로그래머스] 더 맵게(python) Programmers, 더 맵게 TL;DR 힙(heap) 문제 요약 1. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 갖고 있는 음식을 섞어서 스코빌 지수를 늘리려고 한다. 2. 갖고 있는 음식 중 스코빌 지수를 가장 낮은 두 개의 음식을 아래와 같은 방법으로 섞어 새로운 음식을 만든다. `섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째 맵지 않은 음식의 스코빌 지수 * 2)` 3. 갖고 있는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. - 보유 하고 있는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 스코빌 지수가 가장 낮은 2개 음식을 뽑아 주어진 공식에 맞게 섞는 것을 반복하면 된다. - 파이썬에서는 힙(heap)이 최소 힙(min hea..
[리트코드] Kth Largest Element in an Array(python) 리트코드, K-th Largest Element in an Array_k번째 큰 원소 TL;DR 힙(heap) 문제 요약 1. 주어진 숫자 배열 nums와 k에 대해서 배열에서 k번째로 큰 원소를 반환한다. 2. k번째 큰 원소는 k번째 개별 원소가 아닌 정렬된 상태에서 k번째로 큰 원소를 의미한다. 입출력 형태 - 예시 1의 경우, 내림차순으로 정렬하면 [6, 5, 4, 3, 2, 1]이 된다. 이 중 2번째로 큰 수는 5이다. - 예시 2의 경우, 내림차순으로 정렬하면 [6, 5, 5, 4, 3, 3, 2, 2, 1]이 된다. 이 중 4번째로 큰 수는 4이다. 풀이 우선, 단순 리스트를 정렬한 후 해당하는 원소를 조회하는 방법으로 해결할 수 있다. class Solution: def findKthLa..

티스토리툴바