# priority queue

56개의 포스트

1781. 컵라면

시간 제한: 2초메모리 제한: 256MB마지막에 풀 문제부터 시작해서 거꾸로 조사하면, 매 단계에서 풀 수 있는 최적의 문제를 선택할 수 있다. 즉, Greedy 하게 풀면 된다.마지막 시간부터, 시간 0까지 단위 시간별로 풀 문제를 다음에 따라 선택한다.1\. 현재

6일 전
·
0개의 댓글

1202. 보석 도둑

시간 제한: 1초메모리 제한: 256MB논리적으로, 작은 가방부터 가능한 최대 가치를 담으면 효율적이다. 이때, Navie 하게 찾으면 시간이 오래 걸린다. 빠르게 후보 보석들을 찾아내고 선택해야 한다.작은 가방부터 순차적으로 다음을 반복한다.1\. 현재 가방 무게에서

7일 전
·
0개의 댓글
post-thumbnail

[BOJ] 11279 최대 힙

https://www.acmicpc.net/problem/11279아이디어우선순위 큐 사용 !

2022년 5월 6일
·
0개의 댓글
post-thumbnail

[BOJ] 2109 순회강연

https://www.acmicpc.net/problem/2109아이디어아이디어가 바로 떠오르지 않아 좀 고민했는데 잘 풀었다~우선순위 큐를 사용해서 fee 기준 내림차순 정렬 후, queue.poll()의 day가 3이라면, 3일 안에 즉 1, 2, 3일에

2022년 5월 3일
·
0개의 댓글
post-thumbnail

[Java/Collection] Stack과 Queue(feat. Priority Queue, Deque)

스택과 큐, 그리고 특수한 큐를 곁들여서...

2022년 4월 29일
·
0개의 댓글
post-thumbnail

[BOJ] 1715 카드 정렬하기

https://www.acmicpc.net/problem/1715아이디어합친 카드 묶음이 계속해서 더해지므로, 작은 숫자 카드 묶음부터 골라야 한다.Priority Queue를 사용하여 가장 작은 두 수를 꺼내서 더하고, 더한 수를 다시 queue 안에 넣었다

2022년 4월 29일
·
0개의 댓글
post-thumbnail

[Leetcode]406. Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people\[i] = $h_i$, $k_i

2022년 4월 13일
·
0개의 댓글

Leetcode - 1337. The K Weakest Rows in a Matrix

2차원 배열이 주어지고 각 row에 해당하는 배열의 1갯수가 작은 순서대로 k개만큼 출력하기, 출력하는 값은 row의 index번호.배열을 sorting해도 되지만 그러면 무조건 O(N log N)이다. 문제가 sorting된 배열에서 가장큰 값 k개만 요구하므로, 모

2022년 4월 11일
·
0개의 댓글

[C] 우선순위 큐(Heap) 및 Heap Sort 구현

heapify의 sift down동작과 sift up동작을 재귀함수로 구현함으로써, heapify, heap_push, heap_pop동작을 간결하고 아름답게 구현할 수 있었다. NOTE: must check l_idx < h_size in advance.So,i

2022년 4월 9일
·
0개의 댓글

[c++] 백준 1655, 가운데를 말해요

백준 1655알고리즘 분류 : priority queue (우선순위 큐)정수를 하나씩 입력받을 때마다, 그때의 중간값을 각각 출력하는 문제다. (만약 입력받은 수의 개수가 짝수개라면, 중간에 있는 두 수 중에서 작은 수를 출력한다.)두 개의 우선순위 큐를 이용하여 문제

2022년 3월 21일
·
0개의 댓글

[c++] 백준 11286, 절댓값 힙

백준 11286 알고리즘 분류 : priority queue (우선순위 큐) 입력받은 정수(0이 아닌)의 절댓값을 오름차순 정렬하고, 0을 입력받을 때마다 절댓값이 가장 작은 값을 출력하면 되는 문제다. (절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를

2022년 3월 18일
·
0개의 댓글
post-thumbnail

[백준] 11279번 최대 힙 - PYTHON

11279번 최대 힙문제 자체는 간단하다.최대 힙을 구현해서 0이 입력되면 pop연산을 자연수가 입력되면 insert연산을 수행한다.배열이 비어있는 경우에 pop연산을 요구하면 0을 출력한다.풀이 1은 직접 최대 힙 자료구조를 구현하는 것이다.MaxHeap이라는 클래스

2022년 3월 16일
·
0개의 댓글

백준 1822 차집합

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.arrayA, arrayB를 모두 입력받은 뒤 A 배열의 요소를 arrayB에서 Linear Search 해서 result 배열

2022년 2월 14일
·
0개의 댓글

백준 1431 시리얼 번호

문제 >수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우

2022년 2월 9일
·
0개의 댓글

백준 18870 좌표 압축

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1,

2022년 2월 9일
·
0개의 댓글

백준 2110 공유기 설치

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에,

2022년 1월 27일
·
0개의 댓글
post-thumbnail

[ Python_Algorithm ] 데크 (Deque) & 우선순위 큐

데크는 더블 엔디드 큐의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상 자료형(ADT)이다.데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며 스택과 큐의 특징을 모두 가지고 있다. 이 추상 자료형의 구현은 배열이나 연결 리스트 모

2022년 1월 24일
·
0개의 댓글
post-thumbnail

Priority queue

Queue 는 FIFO (first in first out) 로 들어온 순서로 정렬된다. 이와 달리 Priority Queue 는 우선 순위가 높은 순서대로 정렬된다. root node 의 우선 순위가 제일 높기 때문에 설정한 우선 순위에 따라 원하는 값을 O(1) 시

2022년 1월 21일
·
0개의 댓글
post-thumbnail

우선순위 큐

힙을 이용하여 우선순위 큐를 구현하는 방법을 알아보자!

2022년 1월 20일
·
0개의 댓글
post-thumbnail

백준 11286, 절댓값 힙 - Heap / PriorityQueue

https://www.acmicpc.net/problem/19271) x != 0 인 경우PriorityQueue에 x 추가=> 최소 절댓값이 먼저 오도록 정렬2) x == 0 인 경우PriorityQueue가 not empty=> PriorityQueue에서

2022년 1월 12일
·
0개의 댓글