그리디(탐욕법)이란?
매 순간 가장 좋아보이는 선택을 하는 알고리즘이다.
현재 상황에서 최선인 선택을 반복하여 결과적으로 최적 해를 구하기 위한 전략이다.
그리디는 언제 사용하는가?
그리디는 아래 두 가지 속성을 만족할 때에만 사용할 수 있다.
1. 그리디 선택 속성 (Greedy Choice Property)
지금의 최선 선택이 전체 최적해의 일부여야 함
2. 최적 부분 구조 (Optimal Substructure)
문제의 최적해가 부분 문제의 최적해로 구성됨
판단 예시
1. 회의실 배정
하나의 회의실에서 N개의 회의를 진행하려고 한다.
각 회의는 시작 시간과 종료 시간이 주어진다.
겹치지 않게 최대한 많은 회의를 선택하라.
종료 시간이 가장 빠른 회의를 선택하는 것이 항상 최적이므로 그리디로 풀 수 있는 문제이다.
2. 동전 교환
동전의 종류가 다음과 같다.
1원, 3원, 4원
금액 N원이 주어질 때 최소 동전 개수를 구하라.
큰 동전부터 고르는 전략이 항상 최적이 아니다. 예를 들어 6원을 만드는 경우 4 + 1 + 1과 3 + 3 중에 두 번째가 개수가 더 적다. 따라서 가장 큰 동전부터 고르는 것이 최적 해를 보장하지 않는다.
3. 큰 수 만들기
숫자 문자열이 주어지고 그 중 K개의 숫자를 제거해서 만들 수 있는 가장 큰 수를 구하라.
예) 4177252841, K = 4
숫자를 크게 만드려면 앞자리 숫자가 커야 하므로 앞에서 부터 작은 숫자를 제거하면 최적 해를 만들 수 있다. 따라서 그리디로 풀 수 있다.
4. 최소 경로 합
N×N 격자에서 좌상단 → 우하단으로 이동한다.
이동은 오른쪽 또는 아래만 가능하다.
각 칸에는 비용이 있다. 이때 최소 경로 합을 구하라.
현재 경로에서 최소 비용을 선택하는 것이 항상 최적 해를 보장하지 않는다. (이후 어떤 칸을 밟을지 모르므로) 따라서 그리디로 풀 수 없다.
관련 문제 풀어보기
[백준] 회의실 배정
- 난이도 : 골드 5
- 문제 링크 : https://www.acmicpc.net/problem/1931
최대한 많은 회의실을 쓰기 위해 종료 시간이 빠른 회의를 먼저 배정해야 한다.
(주의 : 종료 시간이 같은 경우에는 시작 시간이 빠른 회의를 먼저 배정하도록 미리 정렬해준다.)
이후 현재 회의실의 종료 시간 다음에 올 수 있는 회의가 있을 경우 카운트를 증가시키고 다음 종료 시간을 업데이트 한다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0];
const time = input.slice(1).map(t => t.split(' ').map(Number)).sort((a,b) => {
if(a[1] !== b[1]){
return a[1] - b[1]
}else{
return a[0] - b[0]
}
});
let answer = 0;
let curEndTime = 0;
for(let [S, E] of time){
if(curEndTime <= S){
curEndTime = E;
answer++;
}
}
console.log(answer);[백준] A와 B
- 난이도 : 골드 5
- 문제 링크 : https://www.acmicpc.net/problem/12904
문제에서 주어진대로 단순히 S에 A를 더하거나 뒤집고 B를 더하는 방식으로 T를 만드려고 하면 수많은 연산을 해야 한다. (중간에 만들 수 없는 경우도 가지치기 불가능) -> 시간 복잡도가 최대 O(2^1000)이 되어 시간 초과 발생
역으로 T를 S로 만든다고 생각해보면 끝이 A인 경우 A를 제거하고, B인 경우 B를 제거하고 뒤집으면 되므로 한 번에 최대 한 번의 연산만 하면 된다. -> 시간 복잡도 최대 O(T)
즉, 단순 BFS로 접근하면 시간 초과가 발생하지만 현재 상황에서 최적의 선택을 해나가는 그리디를 이용하면 더 효율적으로 풀 수 있다.
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
let S = input[0];
let T = input[1];
while(T.length > S.length){
if(T[T.length-1] === 'A'){
T = T.slice(0, -1); // 끝 A 제거
} else if(T[T.length-1] === 'B'){
T = T.slice(0, -1).split('').reverse().join(''); // 끝 B 제거 + 뒤집기
} else {
break;
}
}
console.log(T === S ? 1 : 0);[백준] 수 묶기
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/1744
설계
1. 오름차순 정렬하기
2. 이전 거랑 현재 거랑 곱하기 (i=1부터 시작, 크기 1이면 바로 출력)
3. 곱한 값이 현재 거보다 커지면 묶기, 같거나 작으면 안 묶기
4. 묶었을 때는 다시 묶으면 안 되므로 i++.
이렇게 하면 0은 음수랑 무조건 곱하고, 음수는 절댓값 큰 값끼리 곱해지고, 1은 곱하지 않고 더하게 된다.
- 실패 이유 : 양수도 큰 수끼리 곱해야 하는데 오름차순으로 곱하면 작은 수부터 곱하게 된다!
=> 음수와 양수를 분리해서 계산해야 한다. (음수는 오름차순, 양수는 내림차순)
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0]
const arr = input.slice(1).map(Number).sort((a,b) => a-b);
if(N === 1){
console.log(arr[0])
return;
}
for(let i=1;i<N;i++){
if(arr[i-1] * arr[i] > arr[i]){
arr[i] *= arr[i-1]
arr[i-1] = 0;
i++;
}else if(arr[i] === 0){
arr[i] = 0;
arr[i-1] = 0;
i++
}
}
console.log(arr.reduce((acc,cur) => acc+cur, 0));- 양수는 내림차순으로 정렬해서 2개씩 곱하기 (홀수 개면 마지막 거 더하기)
- 음수는 오름차순으로 정렬해서 2개씩 곱하기 (홀수 개에 0이 없으면 마지막 거 더하기, 0이 있으면 0과 곱해서 0으로 만들 수 있기 때문에 안 더해도 됨)
- 1은 마지막에 더하기(곱해도 아무 영향이 없으므로 더하는 게 무조건 이득)
- 0은 음수와 곱해서 음수 제거하기
const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input[0]
const arr = input.slice(1).map(Number);
let pos = [];
let neg = [];
let ones = [];
let zeros = [];
for(const x of arr){
if(x > 1) pos.push(x);
else if(x === 1) ones.push(x);
else if(x === 0) zeros.push(x);
else neg.push(x);
}
// 양수 큰 순서
pos.sort((a,b)=>b-a);
// 음수 작은 순서
neg.sort((a,b)=>a-b);
let sum = 0;
// 양수 묶기
for(let i=0;i<pos.length;i+=2){
if(i+1 < pos.length) sum += pos[i]*pos[i+1];
else sum += pos[i];
}
// 음수 묶기
for(let i=0;i<neg.length;i+=2){
if(i+1 < neg.length) sum += neg[i]*neg[i+1];
else if(zeros.length === 0) sum += neg[i]; // 0이 있으면 남은 음수는 0으로 처리 가능
}
// 1 더하기
sum += ones.length;
console.log(sum);[백준] 강의실 배정
- 난이도 : 골드 4
- 문제 링크 : https://www.acmicpc.net/problem/11000
최소 강의실 개수를 구해야 한다.
즉, 강의 시간이 겹치는 강의의 최대 개수를 구해야 한다.
이를 위해 최소 힙을 이용해 가장 빠른 종료 시간을 바로 구할 수 있도록 한다.
- 첫 수업의 종료 시간을 먼저 추가한다.
- 가장 빨리 끝나는 종료 시간보다 같거나 큰 경우 재사용이 가능한 것이므로 pop한 후에 새로운 종료 시간을 push 해준다.
- 가장 빨리 끝나는 종료 시간보다 작은 경우에는 재사용이 불가능하므로 현재 종료 시간을 push 해준다.
- 종료 후의 힙 사이즈가 바로 필요한 강의실의 최소 개수이다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const N = +input[0];
const lectures = input
.slice(1)
.map((line) => line.split(" ").map(Number))
.sort((a, b) => a[0] - b[0]);
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
peek() {
return this.heap[0];
}
push(val) {
this.heap.push(val);
this._up(this.heap.length - 1);
}
pop() {
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this._down(0);
return top;
}
_up(idx) {
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (this.heap[parent] <= this.heap[idx]) break;
[this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
idx = parent;
}
}
_down(idx) {
const len = this.heap.length;
while (true) {
let smallest = idx;
const left = idx * 2 + 1;
const right = idx * 2 + 2;
if (left < len && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if (right < len && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if (smallest === idx) break;
[this.heap[idx], this.heap[smallest]] = [
this.heap[smallest],
this.heap[idx],
];
idx = smallest;
}
}
}
const heap = new MinHeap();
// 첫 수업
heap.push(lectures[0][1]);
for (let i = 1; i < N; i++) {
const [S, T] = lectures[i];
// 가장 빨리 끝나는 강의실 재사용 가능
if (heap.peek() <= S) {
heap.pop();
}
// 현재 수업 종료 시간 추가
heap.push(T);
}
console.log(heap.size());[백준] 센서
- 난이도 : 골드 5
- 문제 링크 : https://www.acmicpc.net/problem/2212
집중국을 최대 K개 설치하여 각 집중국의 수신 가능 영역의 합을 최소화 해야 한다.
이때 집중국의 수신 가능 영역은 가장 먼 두 센서 간의 거리와 같다. (ex. 센서 1,3,6이 있다면 수신 가능 영역은 6-1=5)
집중국은 센서 사이에 끊는 지점을 만들어주므로 수신 가능 영역을 최소화하려면 거리가 먼 곳부터 끊어주어야 한다.(집중국 1개 -> 전체 범위 커버, 2개 -> 끊는 지점 1개, 3개 -> 끊는 지점 2개)
- 센서 오름차순 정렬
- 거리 계산
- 거리 내림차순 정렬
- 거리가 큰 K-1개 제거
- 남은 거리 합산
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const N = +input[0]; // 센서 개수
const K = +input[1]; // 집중국 개수
const sensors = input[2]
.split(" ")
.map(Number)
.sort((a, b) => a - b);
const distance = [];
for (let i = 0; i < sensors.length - 1; i++) {
distance.push(sensors[i + 1] - sensors[i]);
}
distance.sort((a, b) => b - a).splice(0, K - 1);
console.log(distance.reduce((acc, cur) => acc + cur, 0));[백준] 수리공 항승
- 난이도 : 실버 3
- 문제 링크 : https://www.acmicpc.net/problem/1449
테이프 개수를 최소로 하기 위해서는 1개의 테이프로 커버 가능한 범위를 최대한 활용해야 한다.
테이프로 커버 가능한 최대 범위는 L - 1이다. (물 새는 곳의 좌우로 0.5씩 간격을 주어야 하므로)
따라서 물 새는 곳 사이의 간격을 새서 테이프로 커버 가능할 때까지 뒤의 인덱스를 늘리고, 더이상 커버가 불가능하면 테이프 개수를 추가하고 인덱스를 갱신하도록 했다.
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, L] = input[0].split(" ").map(Number);
const location = input[1]
.split(" ")
.map(Number)
.sort((a, b) => a - b);
let possible_range = L - 1;
let s = 0;
let e = 1;
let tape = 0;
while (s < N) {
if (e < N && location[e] - location[s] <= possible_range) {
e++;
} else {
s = e;
e++;
tape++;
}
}
console.log(tape);아래처럼 포인터를 1개만 써도 풀 수 있다. (현 위치를 기준으로 커버 가능 끝 범위를 계산, 범위를 벗어나면 테이프 추가, 범위 안이면 다음 위치로 continue)
const fs = require("fs");
const input = fs
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
.toString()
.trim()
.split("\n");
const [N, L] = input[0].split(" ").map(Number);
const location = input[1]
.split(" ")
.map(Number)
.sort((a, b) => a - b);
let tape = 0;
let lastCovered = -Infinity;
for (let i = 0; i < N; i++) {
// 이미 덮인 위치면 넘어감
if (location[i] <= lastCovered) continue;
// 새 테이프 붙이기
tape++;
lastCovered = location[i] + (L - 1);
}
console.log(tape);