그리디 알고리즘 - 현재 상황에서 가장 좋아보이는 것을 선택

그리디 알고리즘 (=탐욕법)

어떠한 문제를 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘!

 

→ 탐욕적 ? 현재 상황에서 지금 당장 좋은 것만 고르는 방법!

 

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

---

그리디 알고리즘 유형

'사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형!'

 

ex) 여러 개의 데이터를 빠르게 정렬해야 하는 문제 → 정렬 라이브러리 사용!

     최단 경로를 빠르게 찾아야 하는 문제 → 플로이드 워셜 or 다익스트라 알고리즘 사용!

 

따라서, 그리디 알고리즘 유형을 대비하기 위해 많은 문제를 푸는게 장땡

(창의력과 아이디어를 요구하는 문제!)

 

→ 기준 ? ex) "가장 큰 순서대로" / "가장 작은 순서대로" 이와 같은 기준을 통해 최적해를 찾아야 한다.

---

그리디 알고리즘 예제

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

 

"그리디 알고리즘의 대표 문제!!"

 

→ 아이디어 ? "가장 큰 화폐 단위부터 거슬러주자!"

 

500원 →100원 → 50원 → 10원 순서대로

 

ex) N = 1260원

 

1. 500원

1260원 >= 500원 x 2 → 따라서, 500원 2개 거슬러주자

 

2. 100원

260원 >= 100원 x 2 → 따라서, 100원 2개 거슬러주자

 

3. 50원

60원 >= 50원 x 1 → 따라서, 50원 1개 거슬러주자

 

3. 10원

10원 >= 10원 x 1 → 따라서, 10원 1개 거슬러주자. 그럼 끝!

 

그러면 이런 문제를 소스코드로 작성하면 어떻게 작성해야 할까?

 

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	int N = 1260, res = 0;
	vector<int> coin = { 500, 100, 50, 10 };

	for (int i = 0; i < 4; i++) {
		res += N / coin[i];
		N %= coin[i];
	}

	cout << "동전 갯수 : " << res << "개";
} 

직접 구현한 코드를 보면 어렵지 않게 구현할 수 있다. 

 

화폐의 종류에 따라 반복문을 돌리고, 각 화폐로 총 금액을 몫 연산하면 거슬러줘야할 동전 갯수가 나온다.

 

또한, 거슬러주고 다음 작은 화폐 단위로 넘어가기 위해 거슬러준 후 금액을 적용하기 위해 나머지 연산을 한다.

---

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 없다!

 

→ 그리디 알고리즘 문제의 해법을 찾았을 경우, 그 해법이 정당한지 검토해야한다! 위와 같은 예제를 보면,

 

'가진 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문'

 

ex) 800원을 거슬러줄 때, 화폐단위가 [500, 400,100] 인 경우일 때, 위와 같은 소스코드로 돌리면 동전 갯수는 4개가 나온다. 하지만, 800 = 400 + 400이므로 또다른 최적해가 나온다. 답은 동전 갯수 2개.

 

따라서, 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출 가능!

 

→ 만약, 코딩 테스트에서 어떤 문제 유형인지 파악하기 어렵다면 우선 '그리디 알고리즘'을 의심하라!

 

의심 순서 : 그리디 → 다이나믹 → 그래프

 

 

 

 

 

출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬 : 취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드