Priority Queue
앞에서 공부 했던 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조다.
우선 순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
우선 순위 큐의 속성
- 모든 항목에는 우선순위가 있다.
- 우선 순위가 높은 원소는 낮은 원소보다 먼저 queue에서 제외된다.
- 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공된다.
- 보통 Heap을 기반으로 구현됨
선언 방법 - Java
// default : 우선순위가 낮은 숫자 먼저 나옴(오름 차순)
PriorityQueue<Integer> pQ = new PrioryitQueue<>();
// 내림차순
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
기본적인 메서드
- add() : PQ에 원소를 추가. 꽉 찬 경우 에러 발생
- offer() : PQ에 원소를 추가. 값 추가 실패시 false를 반환
- poll() : PQ에 첫 번째 값을 반환하고 제거. 비어있으면 null 반환
- remove() : PQ에 첫 번째 값을 반환하고 제거. 비어있으면 에러 발생
- isEmpty() : PQ가 비어있는지 확인 비어있으면 true, 아니면 false
- clear() : PQ를 초기화
- size() : PQ에 있는 원소의 수를 반환
문제 풀어보기
문제 0A: 1927 최소 힙
→ 기본적인 활용 문제 풀어보고 시작하기
문제 0B: 11279 최대 힙
→ 기본적인 활용 문제 풀기
문제 1: BOJ 11286 절댓값 힙
알고리즘 설명
- 절대값이 여러개일 때 처리해주는 것이 중요함! 그거만 잘 처리하면 쉽다.
문제 2A: BOJ 1715 카드 정렬하기
- 큰 숫자를 마지막에 더해주는게 좋음 → 그래야 작은 숫자끼리 더하는거니까
- 그럼 오름차순 정렬 큐를 만들어서 더해주면 된다.
1. 숫자를 입력받는다.(오름 차순)
2. 값 두개를 빼서 더 해주고 결과값에 더해준뒤 다시 큐에 넣어줌
3. 큐에 값이 모두 사라질 때 까지 반복함
문제 2B: BOJ 13975 파일 합치기 3
→ 위와 비슷한 메커니즘으로 푼다.
주의 → 값이 들어가는 개수와 범위를 보고 타입을 잘 설정하기
문제3 : BOJ 1655 가운데를 말해요
tip. 우선 순위 큐를 두개 만든다(오름차순,내림차순)
문제4 : BOJ 1781 컵라면
→ 데드라인을 기준으로 할까 라면 기준으로 계산할까? 데드라인을 기준으로 문제를 푼다면 어떤게 문제?
Tip. 데드라인에 맞춰서 문제를 풀 필요없음
ex)
(데드라인,라면) → (1,10) , (2,100),(4,50) , (4,50), (2,5)
10 + 100 + 5 + 50이 아니라 10 + 100 + 50 + 50으로 가능함
'CS > 알고리즘' 카테고리의 다른 글
Dijkstra algorithm (0) | 2024.01.11 |
---|---|
Backtracking (1) | 2023.10.24 |
Stack & Queue 알고리즘 공부 (1) | 2023.10.14 |