Greedy 대충은 알아서 걍 내가 풀고 싶은대로 풀었지만,,
오늘 아침에 체육복 문제를 1시간 동안 풀다가 너무너무 화가 나고 이게 왜 안 되는지,, 어쩌고 저쩌고
그래서 Greedy 알고리즘을 정리하려고 한다..😂
Greedy 알고리즘
그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중의 선택지라고 가정하는 알고리즘
- Greedy는 '탐욕스러운, 욕심 많은'이라는 뜻
- 그리디 알고리즘은 말 그대로 선택의 순간마다 당장
눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 그리디 알고리즘은 최적해를 구하는 데에 사용되는
근사적인 방법 - 순간마다 하는 선택은 그 순간에 대해서는 최적의 선택일 수 있지만, 그 선택들을 계속 수집해서 최종적인 해답을 만들었다고 해서, 그것이
최적이라는 보장은 없다 - 하지만! 그리디 알고리즘을 적용할 수 있는 문제들은
부분적으로 최적이면서, 최종적으로도 최적인 문제들이다!
눈 앞에 보이는 최적의 상황을 선택하는 예시
가장 큰 값을 알아내는 문제에서,
루트 노드인 '5'에서 다음 노드인 '16'과 '7'을 비교해 보았을 때, 16이 크니까 16을 선택!
하지만, 7을 선택한 후 120을 선택하는 것이 정답!
그리디 알고리즘의 핵심 이론
1. 해답 선택
현재 상태에서 최적의 해답을 선택한다
2. 적절성 검사
선택된 해가 문제의 조건을 만족하는지 검사한다
3. 해답 검사
원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다
알고리즘 적용시 성립되어야 할 조건
- 탐욕적 선택 속성
앞의 선택이 이후의 선택에 영향을 주지 않는다 - 최적 부분 구조
문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다
그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다
근사 알고리즘(Approximation Algorithm)
- 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
- 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있음
그리디 알고리즘 적용 문제
거스름돈 문제
문제 : https://www.acmicpc.net/problem/5585
희수는 자주 잡화점에서 물건을 산다. 잡화점에서 잔돈으로 500원, 100원, 50원, 10원, 5원, 1원이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 희수가 잡화점에서 물건을 사고 1000원 지폐를 한 장 냈을 때, 받을 거스름돈에 포함된 잔돈의 개수를 구하시오
1. 선택 절차
거스름돈의 잔돈 개수를 줄이기 위해 가장 금액이 높은 지폐부터 우선 선택한다
2. 적절성 검사
1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면, 선택한 동전보다 한 단계 작은 동전을 선택해서 1번을 다시 진행한다
3. 해답 검사
선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다
액수가 부족하면 1번 과정부터 다시 반복한다
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
int[] money = {500, 100, 50, 10, 5, 1};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int returnMoney = 1000 - n; //거슬러 줄 돈 구하기
int answer = 0; //잔돈 개수
for(int i=0; i<money.length; i++) {
if(money[i] <= returnMoney) {
//가장 큰 돈으로 줄 수 있는 잔돈 개수 구하기
answer += returnMoney / money[i];
//가장 큰 돈으로는 줄 수 없는 값 다시 넣어주기
returnMoney = returnMoney % money[i];
}
//거슬러줄 돈을 다 계산하면 멈추기
if(n == 0) break;
}
System.out.println(answer);
}
}활동 선택 문제
문제 : https://www.acmicpc.net/problem/1931
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
1. 선택 절차
가장 많은 회의가 진행될 수 있도록, 회의가 빨리 끝나는 것부터 선택한다
2. 적절성 검사
1번 과정을 통해 선택한 시간표가 다른 값들과 겹치지 않는지 검사한다. 만약 겹친다면, 시간표가 겹치지 않는 다른 값을 선택한다.
3. 해답 검사
선택한 값들이 가장 많은 회의를 진행시킬 수 있는지 확인한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][2];
//회의 시간 기록하기
for(int i = 0; i<n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
//회의 시간을 종료 시간이 빠른 순서대로 정렬
//만약 종료 시간이 같다면, 시작 시간이 빠른 순서대로 정렬
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1] == o2[1]) {
return o1[0] - o2[1];
}
return o1[1] - o2[1];
}
});
int count = 0;
int end_time = 0;
//끝나는 시간이 가장 작은 순서대로 count 시작
for(int i = 0; i<n; i++) {
if(end_time <= arr[i][0]) {
end_time = arr[i][1];
count++;
}
}
System.out.println(count);
}
}
