Tutorial : 그리디(Greedy - 탐욕, 욕심쟁이) 알고리즘 timer 1초 memory 512MB

[탐욕(Greedy) 알고리즘]

1. 최적해를 구하는 과정에서 결정을 하는 순간 최적이라고 생각되는 것을 선택해 나가는 것으로 최종해를 얻는 방법이다.    

일반적으로 부분 문제의 최적해가 항상 전체 문제의 최적해에 적용되는 것은 아니나

탐욕 알고리즘으로 해결되는 문제는 부분 문제의 최적해가 전체 문제의 최적해에 그대로 적용​된다.

2. 탐욕알고리즘으로 최적해를 구하는 문제는 다음 두 가지 특성을 만족한다.

  (1) 탐욕적인 선택조건(Greedy Choice Property)

     : 현재 최적이라 선택한 것이 이후의 선택에 영향을 주지 않는다.  (이후에 최적해를 구할때 현재 선택을 번복하는 일이 없다.)

  (2) 최적 부분 구조(Optimal property)

     : 큰 문제의 최적해는 보다 작은 부분 문제의 최적해를 포함한다.  (보다 작은 부분 문제의 최적해가 큰 문제의 최적해에 그대로 사용된다.)

3. 위의 조건을 만족하지 않는경우 탐욕알고리즘은 최적해를 구하는 방법으로 사용하기 어렵다.  이 경우 동적계획법 등 다른 알고리즘을 생각해볼 수 있다.

4. 어떤 문제의 경우, 그리디 알고리즘을 적용하기 위해서는  입력된 데이터를 어떤 기준으로 정렬하는등 전처리가 필요한 경우도 있다.    (예 : 1370 회의실배정)    

[탐욕알고리즘 문제의 예]

: 한쪽에만 추를 올려놓을 수 있는 양팔저울과 1, 2, 4, 16 그램의 추가 각각 10개씩 주어진다.

  89 그램 물체를 측정하는데 최소 추의 개수는 몇개일까?

<고찰>

: 탐욕적인 선택조건을 적용해보고 최적부분 구조를 갖는지 알아본다. 

(1) 먼저 16그램 추를 최대한 사용해본다. 이제 89 - 16 * 5 = 89 - 80 = 9그램 무게가 남는다.

(2) 남은 9그램을 8그램 추로 사용해본다. 그러나 8그램 추는 0개이므로 사용할수 없다.

(3) 그 다음 남은 무게에 4그램 추를 최대한 사용해 본다.

이때 16그램 추를 사용한 것을 번복할 필요가 없다. 이 단계에서 고려해봐도 16그램 추 5개를 선택한 것이 최적해이다.

이제 9 - 4 * 2 = 9 - 8 = 1그램 무게가 남는다.​

(4) 남은 무게 1그램에 2그램 추를 최대한 사용해 본다. 사용할 수가 없다.

남은 무게 1그램에 1그램 추를 최대한 사용해 본다. 이때 이전 단계에서 결정한 것을 번복할 필요가 없다.​

이제 1그램추 1개를 사용하면 된다.

∴ 89그램의 물체는 16그램 추 5개, 4그램 추 2개, 1그램 추 1개. 즉, 8개가 89그램 물체를 측정하는데 필요한 추의 최소개수이다.

결론적으로 이문제는 "탐욕적인 선택조건"을 만족하고 있으며, 전체 문제의 최적해는 부분 문제의 최적해를 적용하여 얻어지므로 "최적부분구조"를 갖는다.

[문제]

1, 2, 4, 8, 16그램 추가 a, b, c, d, e개 주어진다.

N그램 짜리 물건을 측정하는데 추의 개수를 최소로 사용하고자 한다.

사용된 최소 개수의 추를 출력하는 프로그램을 작성하시오.