🔧변경내용🔨

제목	날짜	내용
발행일	23.04.05

📌들어가기에 앞서

해당 포스트는 그리디 알고리즘를 학습한 것을 정리한 내용입니다.

---

🌈 Greedy Algorithm

Greedy는 "탐욕스러운, 욕심 많은" 이란 뜻

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

그리디 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.

Greedy Algorithm 문제 해결 단계

• 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택

• 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사

• 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

---

💻 Greedy Algorithm 적용 예시

이러한 Greedy Algorithm을 우리가 흔히 겪을 수 있는 사례에 적용해보자?

• 이꼬비은 오늘도 편의점에서 열심히 아르바이트하고 있다.
• 손님으로 온 갓형욱은 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다.
• 갓형욱은 계산하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 했다.

이때 이꼬비는 어떻게 거슬러 주어야 할까?

탐욕 알고리즘으로 동전의 개수를 헤아리는 일은, 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다.

거스름돈 960원을 채우기 위해서

1. 먼저, 500원짜리 동전을 한 개 선택
2. 100원짜리 동전을 네 개 선택
3. 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택

이꼬비의 입장에 탐욕 알고리즘의 문제 해결 과정을 적용하면 다음과 같이 문제를 단계적으로 구분할 수 있다.

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택

2. 적절성 검사 :

   • 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사
   • 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택

3. 해답 검사 :

   • 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사
   • 액수가 부족하면 1번 과정부터 다시 반복

이 과정을 통해 얻은 문제에 대한 해답은 다음과 같다.

• 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.

---

마지막으로 한 가지 예시를 더 살펴보자.

🥖$3 40g | 🍞$1.5 25g | 🥯$2.5 5g | 🥐 $2 20g
👜 LIMIT 35g

• 범피스트가 빵 가게에서 빵을 훔치려고 한다.
• 범피스트의 가방은 35g까지의 빵만 담을 수 있고,
• 빵은 가격이 전부 다르며, 4개의 종류가 각 1개씩 있다.
• 빵은 쪼개어 담을 수 있다.
• 장발장은 최대한 가격이 많이 나가는 빵으로만 채우고 싶다.

범피스트가 탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해진다.

1. 가방에 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣는다.

2. 그다음으로 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣는다.

3. 만약, 가방에 다 들어가지 않는다면 쪼개어 넣는다.

	1달러당 무게(반올림)
🥖	13.3g
🍞	16.7g
🥯	2g
🥐	10g

달러당 부피가 가장 작은 빵(무게 대비 가장 비싼 물건)부터 담아야 한다.

1. $1당 2g인 🥯 3번 빵(5g) 먼저 가방에 담을 수 있다: [남은 가방의 무게: 30g]
2. $1당 10g인 🥐 4번 빵(20g)을 다음으로 담을 수 있다: [남은 가방의 무게: 10g]
3. $1당 13.3g인 🥖1번 빵(40g)을 다음으로 담을 수 있다.
   • 그러나, 40g을 온전히 못 채우기 때문에 쪼개어, 10g만 넣는다: [남은 가방의 무게: 0g]
     = $2.5 + $2 + $0.75 ⇒ 범피스트는 최대 $5.25어치의 빵을 훔칠 수 있다.

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.

하지만, 만약 “빵을 쪼갤 수 없는 상황”이라면 마시멜로 실험 결과처럼 Greedy는 최적의 결과를 보장할 수 없다.

무게 대비 가장 비싼 물건을 넣는다는 조건을 두고 현재에 최선을 다하게 되면 빈 자리 5g이 남게 되고 결과를 도출하게 되지만, 빈 자리 5g을 채워 더 큰 최댓값을 만들 수 있는 최선의 상황이 있을 수도 있기 때문이다.

마시멜로 실험이란?
지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만,
전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.

따라서, 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.

탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야 한다.

---

탐욕 알고리즘의 특징

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

• 앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조(Optimal Substructure) :

• 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.

이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

---

🥊 Greedy Algorithm 실전 문제

🎯 거스름돈

[Bronze II] 거스름돈 - 5585

Greedy Algorithm을 적용한 문제 중 가장 대표적인 예제는 거스름돈이다.

거스름돈 예제를 통해 해당 로직이 어떻게 구현이 되는지 알아보도록 하자.

✅ 설명

타로는 자주 JOI 잡화점에서 물건을 산다. JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI 잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

JOI 잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다고 되어 있다.

즉 언제나 거스름돈을 적게 주는 알고리즘을 짜야한다.

예제 1
입력 : 380 / 출력 : 4

예제 2
입력 : 1 / 출력 : 15

타로가 380엔을 지불해야 한다면 타로가 받아야 할 거스름돈은 620엔이다.
그
렇다면 500엔 1개, 100엔 1개, 10엔 2개로 총 4개의 동전을 거슬러 받는 것이 가장 적게 잔돈을 거슬러 받는 방법일 것이다.

가장 적게 거슬러 받기 위한 로직을 작성해보자.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split('\n')

let n = Number(input)
function keepTheChange(input) {

  // 1000엔짜리 지폐를 냈다는 가정이 있고, 입력값으로는 지불해야 할 금액이 들어온다
  let change = Number(1000 - input);
  // 카운트하기 위해 변수 count에 0을 할당 
  let count = 0;

  //입력값에 배열이 들어오지 않으므로 직접 배열을 만들어준다.
  const joiCoins = [500, 100, 50, 10, 5, 1];

  //만든 배열의 개수만큼만 돌려줘야 합니다.
  for (let i = 0; i < joiCoins.length; i++) {
    //거스름돈이 0원이 되면 for 문을 멈춥니다.
    if (change === 0) break;

    //거스름돈과 잔돈을 나눈 몫을 셉니다.(쓰인 잔돈의 개수 세기)
    count += Math.floor(Number(change / joiCoins[i]));
    //거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
    change %= joiCoins[i];

  }

  //count를 리턴합니다.
  return count;
}
console.log(keepTheChange(n))

함수 keepTheChange는 항상 1000엔짜리 지폐를 냈다는 가정이 있고, 입력값으로는 지불해야 할 금액이 들어오기 때문에 변수 change에 1000 - input을 하여 잔돈을 먼저 계산을 해준다.

JOI 잡화점은 항상 잔돈이 충분히 있고 거스름돈 개수가 가장 적게 잔돈을 주어야만 하기 때문에, 가장 금액이 큰 잔돈부터 계산을 시작한다.

그러기 위해서는 가장 금액이 큰 잔돈 순서대로 배열을 만들어 줄 필요성이 있으므로, joiCoins라는 배열을 만들어 큰 잔돈 순서대로 요소를 채운다.

for 문에서는 만든 배열의 요소 개수만큼만 반복문을 돌릴 것이고, if 문에서는 잔돈이 0원이 되면 for 문을 멈추도록 조건을 짠 뒤, 거스름돈이 큰 순서대로 나눠서 몫을 구한다.

count 변수에는 change와 joiCoins[i]를 나눈 몫을 카운트하여 넣어주고, change에는 거스름돈으로 나누어 나온 나머지를 재할당 해준다.

greedy Algorithm은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

따라서 해당 로직은 “거스름돈을 가장 큰 잔돈부터 나눠서 0원으로 만든다" 라는 최적의 상황을 쫓게 되는 것이다.

---

📚 레퍼런스