동빈북 3장 그리디 내용 정리

Greedy라는 단어는 한국어로 번역하면 욕심쟁이 기법이다.

단어에서 느껴지는 뉘양스 그대로 그 상황에서만 최선이 되는 경우를 고르는 알고리즘인데 아무생각없이 보면 그 자리에서 가장 유리한 선택을 하는것이 최적의 답일 것 같다고 생각 할 수 있지만..

인생을 보더라도 항상 그 순간에 최적의 선택을 한다고 그것이 모두 모아놓고 봤을땐 최선이 아니다.

알고리즘도 어찌보면 인생과 비슷하기 때문에 문제마다 전체적으로 보는 것이 중요하다.(물론 인생이 더 복잡하지만..)

아무튼 현재의 선택이 나중에 끼칠 영향을 고려하지 않는다. 그 예제로는 예를들어 배열이 6 10 5 30 6 이렇게 있다고 했을때 연속된 숫자를 고르지 못해 만약 그냥 당장 배열 요소중 하나만 본다고 가정하면 답은 17이 될 것이다.

하지만, 알다시피 그건 답이 아니다. 하지만 분명 그 상태에서 최선을 선택하는 것이 최선의 답인 문제들이 있다.

기준에 따라 좋은 것을 선택하는 알고리즘문제 중 "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 알게 모르게 제시해준다고 한다.

대표적으로 거스름돈 문제가 있다.

간단히 거슬러 줘야하는 돈을 최소의 동전으로 거슬러 줘야 하는 문제이다. 단, 여기서 조건은 500원,100원,50원,10원의 동전으로 거슬러 주며 N은 10의 배수이다.

이 문제는 탐욕기법을 이용하면 간단하게 풀린다. 500으로 나눌 수 있는만큼 나누고 그 다음 100 이런 순서로 연산을 진행하면 된다.

(하지만, 예를들어 동전이 10,40,60원인 경우는 최적이 아니다. 이런 문제에 대해서는 후에 DP 개념에서 언급하도록 하겠다.)

사실, 그리디로 주어지는 대부분의 문제는 이 문제처럼 쉽게 나오지는 않는다..