탐욕 기법

탐욕 (Greedy)

• 최적해를 구하는 데 사용되는 근시안적인 방법
• 최적화 문제란 가능한 해들 중에서 가장 좋은 해를 찾는 문제이다.
• 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
• 선택 시점에서의 결정은 지역적으로는 최적이지만, 최종적인 해답이 최적이라는 보장은 없다.
• 한번 선택된 것은 번복하지 않는다.
  → 대부분의 탐욕 알고리즘은 단순하고 제한적인 문제에 적용

📌탐욕 알고리즘의 필수 요소

• 탐욕적 선택 속성
  • 탐욕적 선택은 최적해로 갈 수 있음을 보여라
• 최적 부분 구조 (optimal substructure property)
  • 최적화 문제를 정형화하라
  • 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.
• [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명해야 한다.

📌대표적인 탐욕 기법 알고리즘

알고리즘	목적	설명	유형
Prim	N개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	서브 트리를 확장하면서 MST를 찾는다	그래프
Kruskal	위와 동일	싸이클이 없는 서브 그래프를 확장하면서 MST를 찾는다.	그래프
Dijkstra	주어진 정점에서 다른 정점들에 대한 최단경로를 찾음.	주어진 정점에서 가장 가까운 정점을 찾으면서 반복해서 찾는다.	그래프

---

💡활동 선택 문제

• 탐욕기법을 적용한 반복 알고리즘
  1) 종료 시간이 빠른 순서로 활동들을 정렬
  2) 첫번째 활동 선택
  3) 선택한 활동의 종료시간보다 빠른 시작 시간을 가지는 활동을 모두 제거
  4) 남은 활동들에 대해 앞의 과정 반복

public class Main {

    static class Meeting implements Comparable<Meeting> {
        int start, end;

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

        @Override
        public String toString() {
            return "Meeting{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }

        @Override
        public int compareTo(Meeting o) {
            int value = this.end - o.end;

            if (value != 0) return value; //끝나는 시간이 다르다면

            //종료 시간이 같으면 시작순서가 빠른순으로 정렬한다.
            // (1,2) (2,3) (3,3) 이렇게
            // (1,2) (3,3) (2,3) 이렇게 정렬하면 앞에 두개만 선택된다.
            return this.start - o.start;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Meeting[] meetings = new Meeting[N];
        for (int i = 0; i < N; i++) {
            meetings[i] = new Meeting(sc.nextInt(), sc.nextInt());
        }

        for(Meeting meeting : getSchedule(meetings)){
            System.out.println(meeting);
        }

    }

    static ArrayList<Meeting> getSchedule(Meeting[] meetings) {
        ArrayList<Meeting> list = new ArrayList<>();
        Arrays.sort(meetings); // 종료시간 기준 오름차순 정렬 
				//comparable을 어떻게 정의하냐에 따라 정렬이 달라진다.
        list.add(meetings[0]);

        for (int i = 1; i < meetings.length; i++) {
            if (list.get(list.size() - 1).end <= meetings[i].start) {
                list.add(meetings[i]);
            }
        }
        return list;
    }
}