그리디(greedy)

그리디 알고리즘

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정

 

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택

2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사

-> 전체 문제를 해결하지 못한다면 1로 돌아가 과정 반복

---

백준 온라인저지 11047번

import java.util.Scanner;

public class P11047_동전개수의최솟값구하기 {

    /**
     * 그리디 알고리즘 : 항상 최적의 해를 보장하지는 않음
     * 문제 분석이 중요함!
     * 이번 문제에서는 동전 가격이 서로 배수가 되므로 반례가 생기지 않아 그리디 알고리즘에 적합함
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

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

        // 최대한 큰 동전부터 사용
        int count = 0;
        for(int i=N-1; i>=0; i--) {
            if(arr[i] <= K) {
                count += (K/arr[i]);
                K = K % arr[i]; // 현재 동전을 사용하고 남은 금액
            }
        }
        System.out.println(count);
    }
}

---

백준 온라인저지 1931번

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

public class P1931_회의실배정하기 {
    public static void main(String[] args) {
        // 현재 회의 종료시간이 빠를수록 더 많은 회의를 진행할 수 있음 -> 그리디
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 회의 개수
        int[][] arr = new int[N][2];

        for(int i=0; i<N; i++) {
            int s = sc.nextInt(); // 회의 시작시간
            int e = sc.nextInt(); // 회의 종료시간

            arr[i][0] = s;
            arr[i][1] = e;
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                if(arr1[1] == arr2[1]) {
                    return arr1[0] - arr2[0];
                }
                return arr1[1] - arr2[1];
            }
        });

        int answer = 0;
        int end = -1;
        for(int i=0; i<N; i++) {
            if(arr[i][0] >= end) {
                end = arr[i][1];
                answer++;
            }
        }
        System.out.println(answer);
    }
}