[멋사 알고리즘 스터디] 23.09.13 - Greedy 알고리즘

Greedy Algorithm 🎃

"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"

그리디 알고리즘, 또는 욕심쟁이 알고리즘, 탐욕 알고리즘 등등으로 불린다.

최적해를 구하는 데에 사용되는 근사적인 방법으로,
여러 경우 중 하나를 결정해야 할 때마다 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

지역적으로는 최적의 답이지만, 그 답들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

📣두 가지 조건 만족

1. 탐욕스런 선택 조건(greedy choice property)
   앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조 조건(optimal substructure)
   문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못하지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있기에, 근사 알고리즘으로 사용할 수 있다.

탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다.

---

백준 11000 - 강의실 배정
https://www.acmicpc.net/problem/11000

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//[그리디] 강의실 배정

class Class{
    int start;
    int end;

    Class(int start, int end){
        this.start = start;
        this.end = end;
    }
}

public class Main {
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();
        Class[] classes = new Class[N];
        for (int i=0; i<N; i++){
            int start = s.nextInt();
            int end = s.nextInt();
            classes[i] = new Class(start, end);
        }

        Arrays.sort(classes, (c1, c2) -> c1.start == c2.start ? c1.end - c2.end : c1.start - c2.start);

        PriorityQueue<Integer> end = new PriorityQueue<>();
        end.offer(classes[0].end);

        for (int i=1; i<N; i++){
            if (end.peek() <= classes[i].start){
                end.poll();
            }
            end.offer(classes[i].end);
        }

        System.out.println(end.size());


    }
}

물론 강의가 있을 때마다 강의실을 내줄 수 있겠지만 그것은 최적의 답이 아니다. 강의 시간에 맞춰 최소의 강의실을 내주도록 만들자!

1. 주어진 강의 시간들을 오름차순으로 정렬해준다. 만약 시작 시간이 같으면 끝나는 시간 순으로 정렬해준다.
   • (4 / 9) , (4 / 8) -> (4 / 8) , (4 / 9)
2. 우선순위 큐를 사용하여 끝나는 시간을 추가해주고, 다음 강의의 시작하는 시간과 비교하여 해당 강의실에서 진행할 수 있는지를 판단하고, 진행 가능 하다면 끝나는 시간을 업데이트 해준다.
   • 우선순위큐 -> 3 / 5 / 7
     다음 강의가 ( 4 / 8 ) 이라면 3시에 끝나는 강의실에서 이어서 진행할 수 있으므로 그 다음 우선순위 큐는 5 / 7 / 8 의 형태가 된다.
     다음 강의가 오름차순 이므로 ( 4 / 9 ) 이라면 해당 강의 시작
     시간이 우선순위큐에 있는 끝나는 시간보다 이르므로 새로운 강의실을 사용해야한다!
     그렇다면 마지막 우선순위큐는 5 / 7 / 8 / 9 의 형태가 된다.
3. 우선순위큐의 크기는 사용하는 강의실의 개수가 되므로 해당 크기를 출력해준다.

✨그리디 문제를 풀면서 알게 된 점은 정해진 알고리즘 규격이 없다는 것! 최적의 답을 구하기 위한 방법을 더 생각해보자.