동블

그래프 뷰

15. 그리디

4 min read

그리디

Summary

그리디는 “지금 최선의 선택이 전체 최선이 되는가”를 확인해야 하는 유형이다.
코테에서는 보통 정렬과 함께 나온다. 정렬 기준을 잘못 잡으면 바로 틀린다.

그리디 의심 신호

표현처리
정렬 후 앞에서부터 선택회의실 배정, 활동 선택
끝나는 시간 기준 정렬최대 개수 선택
작은 것부터 / 큰 것부터로프, 동전, 거스름돈
교환해도 손해 안 봄(교환 논증)그리디 성립 근거

Warning

“그리디 같다”고 바로 짜지 말고, 반례가 없는지 먼저 의심한다.
반례가 떠오르면 DP를 고려한다.

회의실 배정 검증 템플릿

Info

끝나는 시간 오름차순 정렬 후, 시작 시간이 직전 끝 시간 이상이면 선택한다.
끝나는 시간이 같으면 시작 시간 오름차순으로 정렬해야 안전하다.

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
 
        int[][] meet = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meet[i][0] = Integer.parseInt(st.nextToken());
            meet[i][1] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(meet, (a, b) -> {
            if (a[1] == b[1]) return Integer.compare(a[0], b[0]); // 끝 같으면 시작 오름차순
            return Integer.compare(a[1], b[1]);                   // 끝나는 시간 오름차순
        });
 
        int end = 0, count = 0;
        for (int[] m : meet) {
            if (m[0] >= end) {       // 직전 회의 끝난 뒤 시작 가능
                count++;
                end = m[1];
            }
        }
 
        System.out.println(count);
    }
}

로프 (최댓값 그리디)

Info

N개 중 일부를 묶으면 묶음 중 최소 굵기 * 개수가 들 수 있는 무게다.
내림차순 정렬 후 arr[i] * (몇 번째까지 묶었는지)의 최댓값을 본다.

Arrays.sort(arr);   // 오름차순
 
int answer = 0;
for (int i = 0; i < n; i++) {
    // arr[i]를 최소 굵기로 쓰면, i부터 끝까지 (n - i)개를 묶을 수 있다
    answer = Math.max(answer, arr[i] * (n - i));
}

주의점

실수주의
정렬 기준 오선택무엇을 기준으로 정렬할지 먼저 결정
끝 시간 동률 처리시작 시간 보조 정렬로 안전하게
반례 미확인교환 논증이 안 되면 DP 의심
a - b 비교overflow. Integer.compare() 사용
비용/개수 합클 수 있으면 long

백지 복원

1. 회의실 배정은 무엇을 기준으로 정렬하는가?
2. 끝나는 시간이 같을 때 어떻게 정렬하는가?
3. 그리디가 의심될 때 DP로 넘어가야 하는 신호는?

관련 문서