# 그리디 알고리즘(Greedy)

## 그리디 알고리즘이란?

- 최적해를 구하기 위해 선택할 때마다 그 순간에 가장 좋은 선택을 하는 알고리즘
- 각 단계에서의 최적해가 전체 문제의 최적해인 경우에 사용할 수 있는 알고리즘으로, 최적화 문제를 해결하는데 사용된다
- 원리
1. 문제를 부분 문제로 분할한다
2. 각 단계에서 최적해를 선택한다
3. 선택한 최적해를 현재의 부분 문제에 대한 해답에 추가한다
4. 부분 문제가 해결될 때까지 반복한다
- 장점
- 실행 속도가 빠르며, 구현이 간단하다
- 일부 문제에서는 최적해를 항상 보장하며, 이 경우 다른 알고리즘에 비해 더욱 효율적이다
- 대부분의 경우 그리디 알고리즘은 근사해(Approximate Solution)를 구하는 용도로 사용될 수 있다
- 단점
- 그리디 알고리즘은 항상 최적해를 보장하지 않는다. (각 단계에서 선택한 선택지가 다음 단계에서 선택할 수 있는 최선의 선택이라는 보장이 없기 때문)
- 그리디 알고리즘은 전체적인 상황을 고려하지 않고 각 단계에서 가장 좋은 선택을 하는 알고리즘이기 때문에, 전체적인 최적해와는 상충될 수 있다

## 그리디 알고리즘 예시

1. 거스름돈 문제
- 손님이 지불한 돈과 물건의 가격이 주어졌을 때, 거스름돈으로 사용할 동전의 최소 개수를 구하는 문제
- 백준 알고리즘 5585번 ==[링크](https://www.acmicpc.net/problem/5585)==
2. 회의실 배정 문제
- 여러 개의 회의가 있을 때, 각 회의의 시작시간과 종료시간이 주어졌을 때, 가장 많은 회의를 할 수 있는 경우의 수를 구하는 문제
- 백준 알고리즘 1931번 ==[링크](https://www.acmicpc.net/problem/1931)==
3. 크러스컬 알고리즘 (Kruskal Algorithm)
- 최소 비용 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘으로, 간선의 가중치가 작은 순서대로 연결하는 그리디 알고리즘
4. 다익스트라 알고리즘 (Dijkstra Algorithm)
- 최단 경로를 구하는 알고리즘으로, 시작점에서부터 가장 짧은 거리에 있는 정점을 선택해가며 최단 경로를 찾아가는 그리디 알고리즘

> 현재 상태에서 최적이라고 생각되는 선택을 하면서 전역 최적해를 찾을 수 있는지 확인해야한다.

### 거스름돈 문제

- 백준 알고리즘 5585번 ==[링크](https://www.acmicpc.net/problem/5585)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 거스름돈 문제 수도코드 예

1. 지불 금액을 입력받는다.
2. 거스름돈 총액을 계산한다 (1000 - 지불 금액).
3. 화폐 단위 배열을 정의한다 (예: {500, 100, 50, 10, 5, 1}).
4. 거슬러 줄 동전 개수를 초기화한다 (예: coinCount = 0).
5. 각 화폐 단위에 대해 다음을 수행한다.
    a. 거스름돈 총액에서 해당 화폐로 거슬러 줄 수 있는 최대 동전 개수를 누적한다.
    b. 거스름돈 총액을 업데이트한다.
6. 거슬러 줄 동전 개수를 출력한다.

#### 거스름돈 문제 소스코드 예

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int payment = sc.nextInt(); // 지불 금액 입력
        int change = 1000 - payment; // 거스름돈 총액 계산

        int[] coins = {500, 100, 50, 10, 5, 1}; // 화폐 단위 배열
        int coinCount = 0; // 거슬러줄 동전 개수

        for (int coin : coins) {
            coinCount += change / coin; // 해당 화폐로 거슬러 줄 수 있는 최대 동전 개수 누적
            change %= coin; // 남은 거스름돈 갱신

            if (change == 0) break; // 거스름돈이 없으면 종료
        }

        System.out.println(coinCount); // 거슬러 줄 동전 개수 출력
    }
}

### 회의실 배정 문제

- 백준 알고리즘 1931번 ==[링크](https://www.acmicpc.net/problem/1931)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자

#### 회의실 배정 문제 수도코드 예

1. 회의의 수 N을 입력받는다.
2. N개의 회의에 대한 정보(시작 시간, 종료 시간)를 입력받아 리스트에 저장한다.
3. 회의를 종료 시간이 빠른 순으로 정렬한다. 종료 시간이 같을 경우 시작 시간이 빠른 순으로 정렬한다.
4. 현재 시간을 0으로 초기화한다.
5. 사용할 수 있는 회의의 수를 0으로 초기화한다.
6. 정렬된 회의 리스트를 순회하면서 다음을 수행한다.
    a. 현재 회의의 시작 시간이 현재 시간보다 크거나 같다면,
    b. 현재 회의를 사용할 수 있는 회의로 선택하고, 현재 시간을 현재 회의의 종료 시간으로 갱신한다.
    c. 사용할 수 있는 회의의 수를 1 증가시킨다.
7. 사용할 수 있는 회의의 총 수를 출력한다.

#### 회의실 배정 문제 소스코드 예

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 회의의 수 입력
        int[][] meetings = new int[N][2]; // 회의 정보 저장 배열

        for (int i = 0; i < N; i++) {
            meetings[i][0] = sc.nextInt(); // 시작 시간
            meetings[i][1] = sc.nextInt(); // 종료 시간
        }

        // 회의 종료 시간 기준 정렬, 종료 시간이 같다면 시작 시간 기준 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) return a[0] - b[0];
            return a[1] - b[1];
        });

        int count = 0;
        int currentTime = 0;
        
        for (int i = 0; i < N; i++) {
            int[] meeting = meetings[i];
            if (meeting[0] >= currentTime) {
                currentTime = meeting[1];
                count++;
            }
        }
        
        System.out.println(count); // 사용할 수 있는 회의의 최대 개수 출력
    }
}