Greedy: 그리디

이번 기회에는 그리디 알고리즘에 대해 알아보자.

---

그리디 알고리즘.

Greedy: 탐욕스러운, 욕심 많은

문제 해결을 위해 지금 당장 최선의 선택을 하는 것을 바탕으로, 문제의 정답을 구하는 것을 목표로 하는 알고리즘이다.
치명적인 단점으로는, 순간순간 최선의 선택을 하더라도 결과는 최적이 아닐 수 있다는 것이다.

예시를 들어보자.

대한민국의 화폐 중 동전은 현행 기준 10원, 50원, 100원, 500원의 4종류가 있다.
어느 가게의 알바가 손님에게 줘야 할 거스름돈이 980원이라면, 과연 어떻게 거슬러줘야 동전의 개수가 가장 적을까?
980원에서 500원(500 × 1)을 빼고, 남은 480원에서 400원(100 × 4)을 빼고, 남은 80원에서 50원(50 × 1)을 빼고, 남은 30원을
전부 10원짜리 3개로 거슬러 주면 총 9개의 동전으로 답을 구할 수 있으며, 이는 이 문제의 최적해다.

그럼, 다른 경우를 생각해보자.

다른 세계선의 대한민국은 동전 화폐가 10원, 40원, 90원, 100원, 500원의 5종류가 있다고 치자.
위의 대한민국의 경우와 같은 방식으로 해답을 구해본다면
980원에서 500원(500 × 1)을 빼고, 남은 480원에서 400원(100 × 4)을 빼고, 남은 80원을 전부 40원짜리 2개로 거슬러 주면
총 7개의 동전으로 답을 구할 수 있다.

그렇지만 이 문제의 최적해는 6개(500 × 1, 100 × 3, 90 × 2)다.
따라서, 이 경우는 그리디로는 정답을 구할 수 없는 문제라고 할 수 있다.

이유가 무엇일까?

---

그리디 알고리즘이 성립하기 위해서는 다음의 두 조건을 충족해야 한다.

• 탐욕 선택 속성(Greedy Choice Property): 매 단계에서의 탐욕적 선택이 어떤 최적해에 포함될 수 있다.
• 최적 부분 구조(Optimal Substructure): 상위 문제를 하위 문제로 나눌 수 있고, 하위 문제의 최적 문제 해결 방법으로 상위
  문제 또한 해결할 수 있다.

기존의 대한민국에서 거스름돈을 거슬러 줄 때, 맨 처음 500원짜리 1개를 뺐던 걸 확인할 수 있다.
또한 대한민국의 동전 단위는 10원, 50원, 100원, 500원이고, 임의의 동전은 그 동전보다 작은 단위로 쪼개짐을 볼 수 있다.

500원을 100원 이하의 동전들로 구성하면 최소 5개(100 × 5)를 사용해야 하니까, 500원 1개를 사용하는 게 동전 수를 줄이는 방법이다. 남은 480원 또한 같은 방식으로 해결 가능하다.

따라서 기존 대한민국의 거스름돈 문제는 그리디 알고리즘으로 해결할 수 있다.

그러나 다른 세계선의 대한민국은 탐욕 선택 속성에 어긋나기 때문에 그리디 알고리즘으론 해결할 수 없다.
480원을 만들 때 100원을 최대한 많이 쓰려고 4개를 거슬러주면, 최적해와는 다른 답안을 도출하게 된다.

---

그런데, 이 최적 부분 구조. 어디서 본 기억이 있지 않은가?

• 최적 부분 구조(Optimal Substructure): 상위 문제를 하위 문제로 나눌 수 있고, 그것으로 문제 해결이 가능하다.
  피보나치 함수의 경우는, 점화식으로 표현이 가능하다.
• 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복해서(같은 항의 메서드 반복 호출) 해결해야 한다.

앞에서 DP(동적 계획법)를 설명할 때, 피보나치 함수를 예시로 들며 적어놨던 문구다.

DP와 그리디 모두 부분 문제로 분해되는 구조가 보이곤 하지만,
DP는 ‘부분 최적해 조합’이 핵심이고 그리디는 ‘탐욕 선택이 최적해로 이어짐’이 핵심이다.
실제로 사람들은 PS를 할 때, DP와 그리디, 백트래킹 문제들을 많이들 헷갈려 한다. 문제의 조건과 발상이 비슷하기 때문이다.

이제 문제를 하나 풀어보도록 하자.

2839번: 설탕 배달

이미지를 누르면 문제로 이동할 수 있다.

봉지 용량은 5kg와 3kg, 두 종류 뿐이다.

봉지 수를 줄이려면 가능한 5kg 봉지를 많이 사용해야 할 것이다.

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

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

        int totalKg = Integer.parseInt(br.readLine());

        int fiveBags = totalKg / 5;
        int remainder = totalKg % 5;

        while (fiveBags >= 0) {
            if (remainder % 3 == 0) {
                int threeBags = remainder / 3;
                System.out.println(fiveBags + threeBags);
                return;
            }

            fiveBags--;
            remainder += 5;
        }

        System.out.println(-1);
    }
}

5kg 봉지의 개수를 최대로 고정해놓고, 남은 설탕의 무게가 3kg로 나누어 떨어지지 않으면 5kg 봉지 개수를 하나씩 줄인다.

더 이상 5kg 봉지의 개수를 줄일 수 없을 때, 즉 3kg 봉지로만 설탕을 포장해야 할 때인데도 3kg로 나누어 떨어지지 않으면
불가능한 케이스가 된다.

 

DP와 그리디, 백트래킹이 앞으로 자주 헷갈릴거란 발언을 했으니 직접 느껴보았으면 좋겠다.

아래의 문제들은 DP와 그리디를 섞어두었다. 직접 풀어보도록 하자.

 

11399번: ATM

 

2579번: 계단 오르기

 

마찬가지로 이미지를 누르면 문제로 이동할 수 있다.