알고리즘 · 31
욕심쟁이와 우선순위 큐
그때그때 가장 좋아 보이는 것을 고르고, 가장 작은 값을 바로 내주는 큐를 써요.
욕심쟁이는 단계마다 지금 가장 좋아 보이는 것을 고르는 방법이에요.
우선순위 큐는 넣은 차례와 상관없이 가장 작은(또는 가장 큰) 값부터 내줘요.
아래 예제는 카드 묶음 5개를 두 개씩 합쳐 하나로 만들어요.
합칠 때마다 두 묶음의 장수를 더한 만큼 힘이 드는데, 늘 가장 작은 두 묶음을 합치면서 그때 든 힘을 찍고 마지막에 모두 더한 값을 찍어요.
import heapq n = int(input())piles = list(map(int, input().split()))heapq.heapify(piles) # 가장 작은 값이 언제나 맨 앞(piles[0])에 오게 한다 total = 0while len(piles) > 1: a = heapq.heappop(piles) # 가장 작은 두 묶음을 꺼낸다 b = heapq.heappop(piles) cost = a + b print(cost) total += cost heapq.heappush(piles, cost) # 합친 묶음을 다시 넣는다print(total)// 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다function popMin(list) { let at = 0; for (let i = 1; i < list.length; i++) if (list[i] < list[at]) at = i; return list.splice(at, 1)[0];} const t = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = t[0];const piles = t.slice(1, 1 + n); let total = 0;while (piles.length > 1) { const a = popMin(piles); // 가장 작은 두 묶음을 꺼낸다 const b = popMin(piles); const cost = a + b; console.log(cost); total += cost; piles.push(cost); // 합친 묶음을 다시 넣는다}console.log(total);import { readFileSync } from "node:fs"; // 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다function popMin(list: number[]): number { let at = 0; for (let i = 1; i < list.length; i++) if (list[i] < list[at]) at = i; return list.splice(at, 1)[0];} const t: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = t[0];const piles: number[] = t.slice(1, 1 + n); let total = 0;while (piles.length > 1) { const a = popMin(piles); // 가장 작은 두 묶음을 꺼낸다 const b = popMin(piles); const cost = a + b; console.log(cost); total += cost; piles.push(cost); // 합친 묶음을 다시 넣는다}console.log(total);import java.util.PriorityQueue;import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); PriorityQueue<Integer> piles = new PriorityQueue<>(); // 꺼내면 언제나 가장 작은 값이 나온다 for (int i = 0; i < n; i++) piles.add(in.nextInt()); int total = 0; while (piles.size() > 1) { int a = piles.poll(); // 가장 작은 두 묶음을 꺼낸다 int b = piles.poll(); int cost = a + b; System.out.println(cost); total += cost; piles.add(cost); // 합친 묶음을 다시 넣는다 } System.out.println(total); }}using System;using System.Collections.Generic; class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); // (값, 우선순위) 짝으로 넣고, 우선순위가 가장 작은 것부터 나온다 PriorityQueue<int, int> piles = new PriorityQueue<int, int>(); foreach (string w in Console.ReadLine().Split()) piles.Enqueue(int.Parse(w), int.Parse(w)); int total = 0; while (piles.Count > 1) { int a = piles.Dequeue(); // 가장 작은 두 묶음을 꺼낸다 int b = piles.Dequeue(); int cost = a + b; Console.WriteLine(cost); total += cost; piles.Enqueue(cost, cost); // 합친 묶음을 다시 넣는다 } Console.WriteLine(total); }}#include <functional>#include <iostream>#include <queue>#include <vector> int main() { int n; std::cin >> n; // std::greater를 줘야 가장 작은 값이 먼저 나온다(기본은 가장 큰 값) std::priority_queue<int, std::vector<int>, std::greater<int>> piles; for (int i = 0; i < n; i++) { int x; std::cin >> x; piles.push(x); } int total = 0; while (piles.size() > 1) { int a = piles.top(); // 가장 작은 두 묶음을 꺼낸다 piles.pop(); int b = piles.top(); piles.pop(); int cost = a + b; std::cout << cost << '\n'; total += cost; piles.push(cost); // 합친 묶음을 다시 넣는다 } std::cout << total << '\n';}#include <stdio.h> int piles[1000];int count; // 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다int popMin(void) { int at = 0; for (int i = 1; i < count; i++) if (piles[i] < piles[at]) at = i; int v = piles[at]; piles[at] = piles[--count]; // 빈자리는 맨 끝 값으로 메운다 return v;} int main(void) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &piles[i]); count = n; int total = 0; while (count > 1) { int a = popMin(); // 가장 작은 두 묶음을 꺼낸다 int b = popMin(); int cost = a + b; printf("%d\n", cost); total += cost; piles[count++] = cost; // 합친 묶음을 다시 넣는다 } printf("%d\n", total); return 0;}// 내장 우선순위 큐가 없다. 이만한 크기에서는 가장 작은 값을 직접 찾아 꺼내도 된다popMin(list){ at = 0; 반복 (i = 1; i < list.개수; i++) { 만약 (list[i] < list[at]) { at = i; } } v = list[at]; list.자리빼기(at); 돌려주기 v;} n = 콘솔.줄읽기().수로변환();piles = 콘솔.수들읽기(); total = 0;동안 (piles.개수 > 1){ a = popMin(piles); // 가장 작은 두 묶음을 꺼낸다 b = popMin(piles); cost = a + b; 콘솔.쓰기(cost); total += cost; piles.넣기(cost); // 합친 묶음을 다시 넣는다}콘솔.쓰기(total);5 4 3 2 6 1
3 6 10 16 35
핵심
- 욕심쟁이는 뒤를 내다보지 않고 지금 가장 좋은 것을 골라요.
예제에서는 가장 작은 두 묶음이에요.
먼저 합친 묶음은 뒤에서 합칠 때 또 더해지니, 작은 것을 먼저 합쳐야 여러 번 더해지는 수가 작아요. - 욕심쟁이가 맞지 않는 문제도 있어요.
4원·3원·1원 동전으로 6원을 만들 때 큰 동전부터 쓰면 4 + 1 + 1로 3개지만, 3 + 3이면 2개예요.
500·100·50·10원 동전은 큰 것부터 써도 맞아요. - 그래서 욕심쟁이로 풀기 전에, 작은 입력에서 모든 경우를 해 본 답과 견줘 봐요.
한 번이라도 다르면 그 규칙은 틀린 거예요.
예제의 규칙은 작은 입력 3,000개에서 모두 같았어요. - 예제는 가장 작은 두 값을 꺼내고 합친 값을 다시 넣는 일을 되풀이해요.
새 값이 계속 들어와서 처음에 한 번 정렬해 두는 것으로는 안 돼요.
이럴 때 우선순위 큐를 써요. - 우선순위 큐는 속에서 값을 힙이라는 모양으로 둬요.
맨 앞 값이 가장 작다는 것만 지키고 나머지는 정렬해 두지 않아서, 넣고 꺼낼 때 전체를 훑지 않아요. - JavaScript·TypeScript·C·크레이콘에는 내장 우선순위 큐가 없어요.
예제는 꺼낼 때마다 목록을 훑어 가장 작은 값을 찾아요.
이만한 크기에서는 그래도 돼요.
언어별로 쓰는 법
| Python | import heapq — 목록을 heapq.heapify(piles)로 힙으로 바꾸고 heappush(piles, x), heappop(piles).작은 값부터만 나와서, 큰 값부터 꺼내려면 -x를 넣고 꺼낸 뒤 부호를 되돌려요 |
|---|---|
| JavaScript | 내장 우선순위 큐가 없어요. 예제처럼 가장 작은 값의 자리를 찾아 splice(at, 1)로 꺼내고, 값이 많으면 힙을 직접 만들어요 |
| TypeScript | JavaScript와 같아요 |
| Java | PriorityQueue<Integer> — add(x), poll()(꺼내기), peek()(보기만).작은 값부터 나오고, 큰 값부터는 new PriorityQueue<>(Comparator.reverseOrder()).비어 있을 때 poll()은 null을 줘요 |
| C# | PriorityQueue<int, int> — Enqueue(값, 우선순위), Dequeue(), Peek().우선순위가 작은 것부터 나와서, 큰 값부터는 우선순위에 -x를 줘요.비어 있을 때 Dequeue()는 InvalidOperationException |
| C++ | <queue>의 std::priority_queue<int>는 큰 값부터 나와요.작은 값부터는 std::priority_queue<int, std::vector<int>, std::greater<int>>.top()으로 보고 pop()으로 빼요(pop()은 값을 돌려주지 않아요) |
| C | 내장 우선순위 큐가 없어요. 예제처럼 배열에서 가장 작은 값을 찾아 꺼내고, 값이 많으면 힙을 직접 만들어요 |
| Craykon | 내장 우선순위 큐가 없어요. 예제처럼 가장 작은 값의 자리를 찾아 자리빼기(at)로 꺼내요.이 방법은 묶음 5,000개까지는 돌았지만 1만 개에서는 너무 오래 걸린다며 멈췄어요. 그럴 때는 힙을 직접 만들어요 |
자주 하는 실수
욕심쟁이가 통하지 않는 문제에 썼어요
const coins = [4, 3, 1];
let left = 6, count = 0;
for (const c of coins) {
count += Math.floor(left / c);
left %= c;
}
console.log(count);→ 3 — 4 + 1 + 1이에요. 3 + 3이면 2개로 돼요
큰 것부터 고르는 규칙이 맞는지 작은 예로 먼저 확인해요.
이런 동전 문제는 금액마다 답을 표에 채워 가는 동적 계획법으로 풀어요.
heapify 없이 heappop을 불렀어요Python
import heapq
piles = [4, 3, 2, 6, 1]
print(heapq.heappop(piles))→ 4 — 가장 작은 1이 아니라 맨 앞에 있던 값이 나왔어요. 오류도 나지 않아요
heapq.heapify(piles)를 먼저 부르거나, 빈 목록에 heappush로 하나씩 넣어요.
std::priority_queue가 작은 값부터 주는 줄 알았어요C++
std::priority_queue<int> piles;
for (int x : {4, 3, 2, 6, 1}) piles.push(x);
std::cout << piles.top() << '\n';→ 6 — 기본은 가장 큰 값이 먼저예요
작은 값부터는 std::priority_queue<int, std::vector<int>, std::greater<int>>로 만들어요.
Python heapq와 Java PriorityQueue는 반대로 작은 값이 먼저예요.
언어마다 다른 점
목록을 훑어 꺼내는 방법은 값이 적을 때만 써요.
이 컴퓨터에서 재 보니 JavaScript로 묶음 1만 개는 1초도 걸리지 않았지만 10만 개는 10초쯤 걸렸고, Python
우선순위 큐가 없는 언어에서 값이 많으면 연습 문제의 풀이처럼 힙을 직접 만들어요.
목록을 훑어 꺼내는 방법은 값이 적을 때만 써요.
이 컴퓨터에서 재 보니 JavaScript로 묶음 1만 개는 1초도 걸리지 않았지만 10만 개는 10초쯤 걸렸고, Python
heapq는 10만 개도 1초가 안 걸렸어요.우선순위 큐가 없는 언어에서 값이 많으면 연습 문제의 풀이처럼 힙을 직접 만들어요.