Greedy 알고리즘이란?

그리디 알고리즘(탐욕적 알고리즘)은 현재 상황에서 가장 좋아 보이는 선택을 반복하여 최적해를 구하는 알고리즘이다.

각 단계마다 그 순간에 가장 큰 이득을 얻을 수 있는 선택을 하고, 그 선택들을 쌓아서 전체 문제의 해답이 된다고 가정을 하는 알고리즘 방식이다.

가장 핵심은 선택의 순간마다 당장 현재 눈앞에 보이는 이득만을 보는 알고리즘이라는 것이다.

조삼모사라는 사자성어가 있는데 원숭이에게 아침에 3개, 저녁에 4개의 음식을 주겠다고 하니 반발을 해서 아침에 4개, 저녁에 3개를 주겠다고 하자 좋아한다.

즉, 똑같은 양을 받지만 그것을 알아차리지 못하는 무지함을 꼬집는 사자성어이다.

하지만 그리디 알고리즘에서는 조삼모사 < 조사모삼 이 된다.

아침 -> 저녁으로 넘어가는 단계에서 첫 단계인 아침에서는 4개를 선택하는 것이 3개를 선택하는 것 보다 현명한 선택이 되는 것이다.

알고리즘의 문제 해결 방법

단계적 구분 방법

1. Solution

- 가능한 모든 해의 집합(제약 사항을 고려하지 않고 문제를 푸는 모든 방법)

2. Feasible Solution

- 제약을 만족하는 해의 집합

3. Objective Function

- 평가 기준(그리디의 선택 기준)

4. Optimal Solution

- 매 단계 최선의 선택으로 구성이 된 해의 집합
- 그리디가 찾는 최종 결과이지만 항상 최적은 아니다.

ex) 동전 거스름 문제

1. Solution : 모든 거스름 방법
2. Feasible Solution : 거스름돈이 정확히 맞는 조합
3. Objective Function : 동전 개수 최소화
4. Optimal Solution : 화폐 단위가 규칙적이라면 그리디 해가 최적이다.

그리디 알고리즘의 보장 조건

1. 탐욕적 선택 속성 (Greedy Choice Property)

• 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.
• 현재 단계에서 가장 좋아보이는 선택(지역적 최적해)을 해도 그것이 전체 최적해(global optiomum)을 구하는데 방해가 되면 안된다.

ex)

• 동전 거스름 문제: 500원, 100원, 50원, 10원처럼 배수가 일정한 경우엔 큰 동전부터 선택해도 전체 최소 개수 가능 → 만족

• But {400, 300, 100} 동전처럼 비정규 단위면 앞선 선택이 나중 선택을 막음 → 속성 불만족

2. 최적 부분 구조 (Optimal Substructure)

• 부분 문제의 최적해가 전체 문제의 최적해를 구성해야한다.

ex)

• 다익스트라 최단 경로 문제의 경우
  A -> B -> C 경로가 최단이라면 A-> B 경로 또한 최단 경로여야한다.

=> 두 가지 조건을 만족해야 그리디 알고리즘으로 최적해를 보장할 수 있다.

그리디 알고리즘의 적용 예시

https://www.acmicpc.net/problem/2839

그리디 알고리즘 구조

그리디 알고리즘의 보장 조건

탐욕적 선택 속성 (Greedy Choice Property)

여기서 그리디한 선택은 가장 큰 봉지인 5kg을 최대한 첫 단계에서 많이 사용하는 것이다.

첫 단계에서 이러한 전략을 사용해도 다음 단계인 3kg을 선택하는 단계에 영향을 주지 않는다.
3kg은 어차피 나머지 kg에 대한 보조 역할이기 때문이다.

이와 마찬가지로 마지막 1kg을 선택하는 단계에서도 3kg을 선택하고 난 이후 나머지를 채우는 역할이기에 첫 번째 보장 조건을 만족한다.

최적 부분 구조 (Optimal Substructure)

18kg을 배달하는 경우 최적의 해(Optimal solution)은 5kg*3 + 3kg이 최적의 해이다.

즉, 15kg을 만드는 최적해 53과 나머지 3kg을 만드는 최적해 31로 구성이 되며, 각각은 모두 최적 부분으로 이루어져 있다.

따라서 두 번째 보장 조건도 만족을 시킨다.

package Greedy;

import java.io.*;

public class boj_2839_S4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 3 ≤ N ≤ 5000
        int N = Integer.parseInt(br.readLine());
        int min = N;

        int temp = N / 3;

        // O(N)
        for (int i = 0; i <= temp; i++) {
            int check = N - 3*i;

            if (check % 5 == 0) {
                min = i + check/5;
                break;
            }
        }

        System.out.println(min == N ? -1 : min);

        br.close();
    }
}

따라서 이 문제의 경우 시간 복잡도는 O(N)이 나오는 그리디 알고리즘으로 풀 수 있다.