그리디(Greedy)

• 욕심쟁이 알고리즘
  👉 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 함
• 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 사용

적용 기준

다음 두 속성 만족 시 적용

1. 탐욕 선택 속성
   • 각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
2. 최적 부분 구조
   • 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우

그리디로 풀리는 문제

• 거스름돈 문제
  • 관련 문제 풀이
  • 동전의 개수를 최소로 해 거스름돈 주는 방법 구하기
  • 동전들이 서로 배수 관계에 있을 때만 그리디로 풀이 가능
  • 풀이
    • 큰 동전부터 남은 거스름돈을 넘지 않도록 지급
• 연속 배낭문제
  • n개이 아이템을 잘라서 배낭에 담을 수 있는 최대 가치 구하기
  • 풀이
    • 용량을 초과하지 않은 범위 내에서 무게 당 가치가 높은 것부터 아이템을 통째로 넣고, 용량을 초과하는 아이템은 잘라서 용량에 맞춰 담는 전략
• 시스템 내부 시간의 합을 최소로 하는 스케줄링 문제 (활동 선택 문제)
  • 관련 문제 풀이
  • 한 명의 작업자가 n개의 작업을 수행할 때, 작업별 시스템 내부 시간의 합을 최소로 하는 작업 순서 구하기
  • 풀이
    • 시스템 내부 시간 = 기다리는 시간 + 작업 시간
    • 작업시간이 짧은 작업부터 시작
• 그래프 문제
  • 최소신장트리 문제
    • Prim 알고리즘, Kruskal 알고리즘
  • 단일 출발점 최단경로 문제
    • 다익스트라 알고리즘

알고리즘 단계

1. 선택 절차
   • 현재 상태에서 최적인 선택 진행
2. 적절성 검사
   • 선택한 항목이 문제의 조건을 만족시키는지 확인
   • 만족하지 않으면 해당 해 제외
3. 해답 검사
   • 모든 선택이 완료되면, 최종 선택이 문제의 조건을 만족시키는지 확인
   • 조건이 만족되지 않으면 해답 아님

DP와의 차이

그리디

• 각 단계에서 최적의 선택을 하는 방식으로 문제 해결
• 성립 조건
  • 탐욕 선택 속성
  • 최적 부분 구조
• 중복 부분 문제 해결 불가능
• 최적이 아닐 수도 있음

DP

• 작은 문제의 해를 기록해 중복 계산을 피하고, 이를 이용해 큰 문제를 해결
• 성립 조건
  • 중복 부분 문제
  • 최적 부분 구조
• 중복 부분 문제 해결 가능
• 최적의 경로를 구할 수 있음
  👉 시간이 오래걸림

👉 DP 설명 포스팅

구현

• 단계마다 최대, 최소를 연속적으로 구해야하는 그리디에서 우선순위 큐를 사용하면 효율적

💡 우선순위 큐

• 우선순위가 높은 아이템을 삭제하는 자료구조

• 구현 방법들
  • 단계마다 최대나 최소 검색 : O(n^2)
    👉 가장 비효율적
  • 미리 정렬한 후 순차적으로 선택 : O(nlogn)
    👉 표준 방법
  • 힙으로 구현한 우선순위 큐 : O(logn)
    👉 가장 효율적

    💡 힙

    • 완전 이진트리로 볼 수 있는 배열 객체
    • 레벨별 순회 방식으로 배열에 인접하게 저장

      • 최대힙 : 부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전이진트리
      • 최소힙 : 부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전이진트리

구현 코드
백준 11047번 문제
👉 백준 11047번 풀이

• 동전 최소 선택 문제(거스름돈 문제) 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, K;
    static int[] worth;
    static int min = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        worth = new int[N];

        for (int i = 0; i < N; i++) {
            worth[i] = Integer.parseInt(br.readLine());
        }
        min();
        System.out.println(min);
    }

    static void min() {
        for (int i = N - 1; i >= 0; i--) {
            if (worth[i] <= K) {
                min += (K / worth[i]);
                K = K % worth[i];
            }
        }
    }
}