바킹독 알고리즘 강의를 보며 정리한 내용입니다.
Greedy = 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘
📌 그리디 알고리즘 풀 때 주의사항
그리디 알고리즘이 맞다는 확신이 있을때만 풀도록 한다.
거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다.
-> 짜서 제출해보고 틀리면 빠르게 손절
100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
-> 일단은 넘어가고 다른 문제를 풀게 없거나 종료 20-40분 남은 시점에 코딩 시작
(개인적으로 매우 공감하는게 예전에 코테 봤을때 완탐 문제를 그리디로 착각해서 풀어버리고 틀린 적이 있었다. 확신이 없으면 손절하자!)
연습문제 1 - BOJ 11047 동전 0
그리디 알고리즘이 성립하는 이유
간단하게 10, 50, 100, 500원 동전만 존재한다고 생각해보자. 우리는 500원 동전을 최대한 많이 써야함을 보여야한다.
(보조정리) 동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용해야 한다. (귀류법) 안 그러면 10/100원 5개 이상은 50/500원 동전으로 대체 가능하고 50원 동전 2개 이상은 100원으로 대체 가능하기 때문이다. 따라서 결론은 500원 동전을 제일 많이 써야한다. (그리디)
결론적으로는 10, 50, 100 동전으로는 490원 까지만 감당 가능하고 500원을 다 사용하지 않을 경우 10, 50, 100원 동전으로 500원 이상 감당해야함
성립하지 않는 경우
ex) 동전 1, 9, 10원으로 18원을 만드는 경우
증명해야될 명제 : 동전을 최소로 소모하려면 10원을 제일 많이 써야한다.
보조 정리 : 동전을 최소로 소모하면서 물건값을 지불하려면 1원 1개 이하, 9원 1개 이하를 사용해야한다.
귀류법 : 안그러면 1원 2개 이상, 9원 2개 이상을 사용하는데 이는 ..? 대체 가능하지 못하다!
연습문제 2 - BOJ 1931 회의실 배정
풀이 : 회의 끝나는 시간을 그리디하게 선택해준다.
그리디 알고리즘이 성립하는 이유
회의가 3시에 끝나는 강의 A, 회의가 4시에 끝나는 강의 B가 존재한다고 하자. B 대신 A를 고른다는 것은 적어도 B를 골랐을 때 만큼의 회의를 보장하고 그 이상의 값도 줄 수 있다.
(참고로 이 문제는 회의 시작시간과 동시에 끝이 날수도 있기 때문에 끝나는 시간이 같으면 시작시간이 빠른 순으로 배열해야함
(1,2), (2,2) 의 경우 (1,2) 진행 후 (2,2) 진행도 가능하기 때문)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
Node[] arr = new Node[n];
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
arr[i] = new Node(start, end);
}
Arrays.sort(arr);
int time = 0;
int answer = 0;
for(int i = 0; i < arr.length; i++) {
if(time <= arr[i].start) {
answer++;
time = arr[i].end;
}
}
System.out.println(answer);
}
static class Node implements Comparable<Node>{
private int start, end;
Node(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Node o) {
if(this.end == o.end) {
return Integer.compare(this.start, o.start);
}
else return Integer.compare(this.end, o.end);
}
}
}연습문제 3 - BOJ 1026 보물
재배열 부등식으로 증명이 가능한 문제
이 자체에 대한 증명은 너무 어려우니 알 필요 없다.
다만 이게 성립함만 기억하자
