그리디 알고리즘

• 문자 그대로 greedy(탐욕적인)이라는 뜻으로 탐욕 알고리즘으로도 불린다.

• 탐욕적이라는 것은 문제를 풀때, 현재 상황에서 가장 좋은 방법만을 고르는 방법이다.

• 즉, 매순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

• 일반적인 상황에서 최적의 해를 보장할 수 없을 때가 많다.

루트 노드부터 시작해 마지막 노드까지 거쳐갈때, 각 노드의 합을 최대로 만들고 싶을 경우

최적의 값은 5,7,9의 경로를 지난 21이 최적의 값이다.

하지만, 그리디 알고리즘은 매순간 선택지에서 가장 최적의 해만을 고르기 때문에 다르게 나옵게 된다.

루트 노드인 5이후 다음 노드 [7, 10, 8] 중에 가장 최적의 값인 10을 선택하게 되고

이후 [4, 3] 중에서 최적의 값인 4를 선택하게 된다.

---

예제 : 거스름돈

1480원 이라는 돈을 500원, 100원, 50원, 10원 4가지 종류의 돈으로 거슬러 준다고 할때
필요한 동전의 개수는?

1. 가장 큰 값인 500원 짜리 2개로 1,000원을 준다 (잔액: 480)

2. 남은 동전 중 가장 큰 값인 100원 짜리 4개로 400원을 준다. (잔액: 80원)

3. 남은 동전 중 가장 큰 값인 50원 짜리 1개로 50원을 준다. (잔액: 30원)

4. 남은 동전 중 가장 큰 값인 10원 짜리 3개로 30원을 준다. (잔액 : 0원)

• 500원 : 2개 / 100원 : 4개 / 50원 : 1개 / 10원 : 3개

---

예제 : 큰 수의 법칙

• 배열에서 주어진 수들을 n번 더해, 가장 큰수를 만드는 알고리즘
  단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 k번 초과할여 더해질 수 없는 것이 특징

• 예를 들어 [2, 5, 6, 1 ,7] 의 배열이 있고 n = 8, k = 3일 경우

• 가장 큰 수 : 7 / 두번째로 큰수 : 6으로

• 7 + 7 + 7 + 6 + 7 + 7 + 7 + 6

• 7 x 6 + 6 x 2 = 54

• 만일 [5, 4, 5, 4]라는 숫자가 있고 n = 7, k = 2일 경우

• 가장 큰 수 : 5 / 두 번째로 큰 수 : 5 이기 때문에

• 5를 7번 곱한 값이 나온다.