그리디(Greedy) 알고리즘

 

📌  그리디 알고리즘이란?

그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'으로, 단순하지만 강력한 문제 해결 방법이다. 우리는 특정 문제를 만났을 때, 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로,

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 

대체로 이러한 기준은 정렬 알고리즘으로 만족시킬 수 있으므로 그리디 알고리즘 문제는 정렬과 짝을 이뤄 출제된다.

 

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 크다. 

그렇기 때문에, 그리디 알고리즘으로 문제의 해결책을 찾았을 때는 그것이 정당한지 검토하는 것이 매우 중요하다.

 

만약 그리디 알고리즘으로 문제를 해결할 수 없다고 생각되면, DP나 그래프로 해결할 수 있을지 고려해 볼 수 있다.

 

 

---

 

 

그럼 이제 예제를 풀어보자.

 

1️⃣  거스름돈

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

 

A. 이는 그리디 알고리즘의 대표적인 문제이다. 해결법은 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것이다. 

아래는 내가 생각해서 짠 코드다.

package org.example;

public class Ex3_1 {

	public static void main(String[] args) {

		int n  = 1260;
		int count = 0;

		count += n / 500;
		n %= 500;

		count += n / 100;
		n %= 100;
		
		count += n / 50;
		n %= 50;
		
		count += n / 10;
        
        System.out.println(count);

	}
}

 

이건 책에 나와있는 코드. 허허 (;＾◇＾;)ゝ

메모리를 잡았지만, 더 확장성있는 코드인 것 같다. 

그리고 나라면 int coin 변수를 따로 만들지 않았을 것 같은데, 이렇게 한 이유는 coinTypes[i]에 2번 접근하는 것보다 변수 하나를 잡는게 시간적인 측면에서 나아서일까? 아니면 그냥 가독성을 위해서..?

그냥 이 분 스타일인 걸 수도 🧐

package org.example;

public class Ex3_1 {

	public static void main(String[] args) {

		int n  = 1260;
		int count = 0;

		int[] coinTypes = {500, 100, 50, 10};

		for (int i = 0; i < coinTypes.length; i++) {
			int coin =  coinTypes[i];
			count += n / coin;
			n %= coin;
		}

		System.out.println(count);

	}
}

 

정당성

거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 예를 들어 800원을 거슬러줘야 하는데, 화폐 단위가 500원, 400원, 100원인 경우를 생각해보자. 이 경우 그리디 알고리즘으로는 답이 4개(500원+100원*3)가 나오는데, 실제로는 2개(400원*2)이 최적의 해이다.

 

 

 

🔗  참고 자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서