[알고리즘] Greedy Agorithms

• Greedy Algorithms이란
  그리디 알고리즘이란 현재 상황에서 가장 좋은 선택지를 고르는 알고리즘이며 탐욕 알고리즘이라고도 부른다.
  현재 상황에서 가장 좋은 결과를 선택한다고 해서 최종적인 결과 도출에 대한 최적해를 보장해 주는 것은 아니다!

그림을 통해 좀 더 자세히 알아보겠다.

 

가장 큰 수 를 찾아야 하는 문제라고 쳤을 때, 우리는 시작에서 부터 6->128로 가는 경로가 가장 큰 수를 찾는 경로라는 것을 직관적으로 알 수 있다. 하지만 그리디 알고리즘을 이용한다면 시작에서 17->23으로 가는 경로를 선택할 것이다.

 

그리디 알고리즘의 두가지 조건

1. 탐욕스러운 선택 조건 Greedy-choice property
   탐욕적인 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.
   하지만 위에서 그리디 알고리즘의 결과로는 최적해가 반드시 나오는 것은 아니라고 했다. 
   위에서 말했던 것처럼 그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아니지만 문제에서 알고리즘을 선택할 때 그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제여야 한다.
2. 최적 부분 구조 조건 Optimal-substructure property
   문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다.
   전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 하나하나의 단계에 대해 최적해가 도출되어야 한다는 것이다.

 

• 거스름돈 문제

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

 

이 문제에서 그리디 알고리즘을 적용하면 가장 큰 단위의 돈부터 생각하자 이다. 만약에 5740원의 돈을 거슬러 줘야 한다면, 가장 큰 단위의 돈을 최대한 많이 사용해야 할 것이다.

def solution(money):
    answer = 0
    change = [500, 100, 50, 10]
    remain = money
    for i in change:
        answer += remain // i
        remain = remain % i
    return answer

 

• Dynamic Programming vs Greedy

 

dp 문제는 보통 bottom-up방식으로 풀지만 이를 top-down방식으로도 풀 수 있다. 이때는 당연히 memoizing을 해야 한다. 

 

다이내믹 프로그래밍 알고리즘은 subproblem을 먼저 해결하고 선택을 하는 반면 그리디 알고리즘은 subproblem을 해결하지 않고 먼저 첫 번째 선택을 한 다음에 문제를 해결한다.

다이내믹 프로그래밍 알고리즘은 주로 bottom-up방식을 사용하고 그리디 알고리즘은 주로 top-down방식을 사용한다. 
그리디 알고리즘을 사용할 때는 각각의 단계에서 최적의 해가 구해질 때만 사용할 수 있다.