Greedy Algorithm

Greedy Algorithm . 탐욕적인 알고리즘.

개인적으로 이론적으로는 간단하나 문제로 풀기 굉장히 어려운 알고리즘이라고 생각한다. 

일단 greedy 알고리즘은 가장 특징적인 값 (큰거나 작은값 등등)을 이용해 답을 구하는 개념이다.

"이 부분에 있어 이러한 조건으로 완성하면 무조건 최선이다." 라는 느낌이 있어야한다.

예를 들면) 이 필통에 작은 연필순으로 넣으면 가장 많은 연필을 넣을 수 있다. 라는 느낌이다.

어떠한 상황에서 가장 크거나 작은 값이 최적이라는 증명이 반드시 필요하기 때문에, 감만 이용해서 greedy 문제로 접근했다간 틀린 반례를 만나기 쉽다.

Greedy : 탐욕스럽다. 뜻과 굉장히 어울리는데 가장 큰값 작은값으로 정렬해서 푼는 경우도 많다.

---

길이가 1 * n 짜리 필통이 있을 때,  각각 길이가 다른 연필이 있을 때 (각각의 사이즈는 1 * alpha), 최대 몇개의 연필을 넣을 수 있을까 ?

예) 17 짜리 필통에 2, 4, 8, 6, 5, 3, 2, 7, 5, 1, 6 연필이 존재한다면,

작은 값부터 넣으면 1, 2, 2, 3, 4, 5 총 6개 넣을 수 있다.

즉 이 문제는 작은 연필 부터 넣으면 가장 많은 연필을 채울 수 있다.

---

예를 들어 coin 문제가 있다. 

동전이 1, 5, 10, 50, 100짜리가 무한히 있을 때, 

정해진 금액을 최소의 동전 갯수로 주는 방법을 구하는 문제다.

이 문제를 그리디로 접근한다면 => 가장 큰 숫자부터 채우면 된다. 

만약 177 값을 만든다면 

100 => 1개, 50 => 1개, 10 => 2개, 5=> 1개, 1=>2 개. 총 7개의 동전을 주면 된다. 

이게 과연 최소 갯수인가? 맞다. 그 이유는 1, 5, 10, 50, 100 은  한 값이 뒤에 숫자를 만들 수 있기 때문이다.

즉) 100을  1로 100개, 5로  20개, 10으로 10개, 50으로 2개 면 완성 가능하다.

즉 100을 사용하지 않는대신 다른 동전을 사용하게 되면 무조건 손해를 본다.

이럴경우는 그리디로 문제를 해결 할 수 있다.

---

하지만 동전이 1, 4, 5 짜리가 있고,

213 값을 만든다고 할 때, 큰숫자 부터 채우는 그리디 알고리즘을 사용한다면

5짜리 => 42개, 1짜리 => 3개 총 45개가 필요하다.

하지만 213을 만드는 최소값은

5짜리 => 40개, 4짜리 => 3개, 1짜리 => 1개로 총 44개의 동전으로 원하는 값을 만들 수 있다. 

---

이처럼 그리디 방식은 조건에 따라, 옳은 방법일 수 있고 아닐 수 있다. 

그렇기 때문에 그리디로 해결 했을 경우 예외가 없는지 꼼꼼하게 체크해야한다.