# 우선순위 큐

42개의 포스트
post-thumbnail

[Programmers][python] 24. 문제풀이 실습 (12): 프로그래머스 더 맵게

프로그래머스 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니

2021년 4월 30일
·
0개의 댓글
post-thumbnail

[Programmers] 15. 기본 자료구조: 트리 (Tree) (4): 이진 트리의 응용 (2): 힙 (heap)

이진 트리의 응용 2 힙 (Heap) 이진 탐색 트리와의 비교 힙의 장점 힙의 연산 힙의 구현 힙의 응용 우선 순위 큐 (Priority Queue) 힙 정렬 (Heap sort)

2021년 4월 29일
·
0개의 댓글

[BOJ 11000] 강의실 배정 (Python)

처음 '수업이 끝나는 시간'을 기준으로 오름차순 정렬을 한 뒤에 2중 for문을 사용하여 최적의 강의실을 구하는 방식으로 접근하였다. 하지만, 당연히 시간 초과가 발생하였다. N은 최대 200,000으로 N^2은 400억이다. N^2이 40,000,000으로 착각하여

2021년 4월 29일
·
0개의 댓글

[BOJ 11000] 강의실 배정(Python)

강의실 배정이 문제는 그리디 알고리즘을 이용해, 가장 수업 시간이 빠른 것들을 선택하는 문제입니다. N이 <= 200000 이므로 최대 NlogN 안에 들어오는 시간 복잡도를 가져야 시간 초과가 나지 않습니다. 정렬 카테고리에서 찾은 문제지만 고작 input을 s

2021년 4월 28일
·
0개의 댓글

[BOJ 2075] N번째 큰 수 (Python)

처음에는 Max Heap 기반 우선순위 큐를 만들어 N x N 표의 모든 원소를 우선순위 큐에 넣어주었고, N-1번 pop한 후 우선순위 큐의 첫 번째 원소를 출력하는 방식으로 접근하였다. 하지만, 메모리 초과가 났다. --> 메모리 초과가 난 이유는 처음부터 우선순위

2021년 4월 28일
·
0개의 댓글
post-thumbnail

[BOJ 2075] N번째 큰 수(Python)

N번째 큰 수메모리를 감안하여 문제를 푸는 것에 익숙치 않아 처음 시도때 실패했습니다. 모든 숫자를 최대 힙에 담아 n번째 나오는 숫자로 답을 구하는 방식이었습니다.1500 \* 1500만큼의 숫자가 힙에 들어가기 때문에 12MB의 메모리안에 들어올 수 없는 방법입니다

2021년 4월 27일
·
0개의 댓글

[BOJ 1520] 내리막 길(Python)

내리막 길이 문제는 DP 혹은 DFS를 이용하여 풀 수 있습니다. 주의할 점은 이 문제가 가장 빠르게 내려가는 것을 요구하는 것이 아닌, 내려갈 수만 있는 경로라면 모두 채택한다는 점입니다.가장 빠르게 내려만 간다면 오히려 쉽게 구현할 수 있습니다. 사방탐색이 아닌 오

2021년 4월 26일
·
0개의 댓글

[BOJ 1781] 컵라면 (Python)

같은 데드라인 문제들 중에서 받을 수 있는 컵라면 개수가 최대인 1문제를 선택해서 푸는 것으로 접근했다. 데드라인 마다 모든 문제들을 탐색하면 O(N²)으로 시간초과를 예상했다. 따라서 우선순위 큐를 이용하자는 생각을 하였고, 맞는 방법이었다. 이렇게 구현했지만 틀렸다

2021년 4월 11일
·
0개의 댓글
post-thumbnail

[자료구조] 우선순위 큐의 활용

힙의 구현결과 : UsefulHeap.h,c우선 순위 큐의 구현결과 : PriorityQueue.h,cusefulHeap.h의 typedef 선언 변경typedef char HData; -> typedef char \* HData;Main.c

2021년 4월 11일
·
0개의 댓글
post-thumbnail

[자료구조] 우선순위 큐 (Priority Queue)

우선순위 큐 (Priority Queue)

2021년 4월 8일
·
0개의 댓글

[BOJ 1202] 보석 도둑 (Python)

링크문제를 파악할 때 Knapsack 문제인 줄 알았으나 아니였다. 가방이 여러개가 있으며 가방 하나에는 딱 하나의 보석만 담을 수 있다는 조건이 있다. 따라서 최대한 비싼 보석을 하나라도 더 훔치는 것이 중요하다.비싼 보석인데 무겁다고 해서 더 싸고 가벼운 보석에게

2021년 4월 8일
·
0개의 댓글

우선순위 큐(Priority Queue)

우선순위 큐 란?큐와의 차이점우선순위 큐의 사용 예시우선순위 큐란 기존의 큐에 우선순위 개념을 더해준 자료구조입니다.큐에 저장된 자료들은 각각의 우선순위에 따라 정렬됩니다.큐와의 차이점을 보여드리기위해 실제로 push하는 장면을 보여드리겠습니다.우선순위 큐의 우선순위는

2021년 3월 27일
·
0개의 댓글

[백준] N번째 큰 수

heapq를 이용하여 거저 먹으려고 하면 메모리 초과라는 철퇴를 맞는 문제이다. 즉, 힙 리스트의 크기를 제한을 두며 풀어야 한다.N번째 큰 수를 구하기 위해선 크기가 N의 최소 힙에서 맨 앞 원소라는 것을 알아야 한다.즉, N의 크기를 지켜가며 push, pop을 하

2021년 3월 27일
·
0개의 댓글

[백준] 절댓값 힙 풀이

sys.input.readline() 함수의 위력을 실감한 문제다.heapq 모듈을 이용하여 문제 조건 그대로 구현해주면 된다.예외사항으론 절댓값이 들어가므로 abs(a), a를 리스트나 튜플로 감싸서 push 해주면 된다. 절댓값이 같은 경우엔 자동으로 두 번째 요소

2021년 3월 27일
·
0개의 댓글

백준 7662 이중 우선순위 큐

백준 7662 c++ set

2021년 3월 22일
·
0개의 댓글

[힙] 백준1655: 가운데를 말해요

교재랑 똑같은 문제다. 제일 작은 수 - 최대힙 - 중간값 - 최소힙 모양이 되게 하자. 조건1: 최대힙 개수 == 최소힙 개수 조건2: 최대힙의 top < 최소힙의 top 중앙값: 최대힙의 top

2021년 3월 17일
·
0개의 댓글

[힙] 백준11286: 절댓값 힙

백준11286: 절댓값 힙

2021년 3월 17일
·
0개의 댓글

[힙] 백준: 최소 힙

백준 1927 최소 힙

2021년 3월 12일
·
0개의 댓글

[힙] 최대 힙

백준 11279 우선순위 큐 STL을 사용

2021년 3월 12일
·
0개의 댓글