[Javascript 코테 대비] 당장 좋은 것만 선택하는 그리디

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)을 읽고 개인 학습용으로 정리한 내용입니다.

당장 좋은 것만 선택하는 그리디

Greedy Algorithm은 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 문제를 푸는 알고리즘이다.

• 매 순간 가장 좋아보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형에 해당한다.
• 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다.
  • 대체로 정렬 알고리즘과 짝을 이뤄 출제된다.

example_1. 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름 돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

💡 문제 해설
'가장 큰 화폐 단위부터' 돈을 거슬러 준다.

📜 .js 답안 예시

let n = 1260;
let count = 0;

// 큰 단위의 화폐부터 차례대로 확인
const coin_types = [500, 100, 50, 10];

for(const coin in coin_types) {
    count += n / coin; // 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin;
}

console.log(count);

그리디 알고리즘의 정당성

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

• 거스름돈 문제가 그리디 알고리즘으로 해결할 수 있는 이유: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.