01. 그리디(Greedy) 알고리즘

 

 

     그리디(Greedy) 알고리즘은 탐욕적인 문제 해결 방법으로 '문제를 해결하려는 상황에서 그 순간순간마다 최적의 상황을 쫓는 알고리즘'입니다. Greedy 방법은 최적의 해 근사값을 빠르게 찾아 줍니다. (단, 항상 최적의 결과를 도출하지는 않습니다.) 탐욕적이라고 불리는 이유는 미래를 생각하지 않고 지금 당장 보이는 것에서 최선의 방법을 선택하기 때문입니다. 

 

 

 

그리디 알고리즘의 대표적인 예시는 거스름 돈 문제, 시간이 주어졌을때 한 사람이 최대한 많이 할 수 있는 수(활동 선택 문제), 배낭 문제에서 사용됩니다.  

동전의 예시를 들자면, 740원을 거슬러 주어야 할때 500원 짜리 1개 , 100원짜리 2개 , 10원짜리 4개로 거슬러 주는 과정에서 "큰 화폐부터 거슬러 준다" 라는 알고리즘을 통해 최적의 해를 보장할 수 있습니다. 

 

 

그리디 알고리즘은 기본적으로 정렬(Sort)와 함께 사용되는 경우가 많습니다.

 

 

 

그리디는 두가지 조건을 성립하면 잘 작동합니다.

 

첫번째

탐욕스러운 선택 조건 (Greedy choice property)

-앞의 선택이 이후의 선택에 영향을 주지 않는다.

 

두번째

최적 부분 구조 조건(Optimal Substructure)

-문제에 대한 최종 해결 방법이 부분 문제에 대해서도 최적 문제 해결 방법이다.

 

 

 

   다음은 그리디 알고리즘의 예시입니다. 최적의 해는 초록색 원인 107이지만, 그리디 알고리즘을 통하면 7과 13중에 13, 5와 11중에 11 이므로 24의 결과를 얻습니다. 다음과 같은 문제에서는 최적해를 보장해주지 않는다는 것을 명심해야 합니다.

 

 

   이렇듯, 모든 문제가 그리디 알고리즘으로 풀 수는 없습니다.  이럴 경우 다이나믹 프로그래밍(Dynamic Programming) 등의 알고리즘 기법을 사용하여 해결할 수 있습니다.

 

*추가

그리디 문제는 대부분 Sort 정렬과 같이 쓰이는 경우가 많은 것 같다.