[알고리즘]그리디 알고리즘 Greedy Algorithm

[ 그리디 알고리즘 Greedy algorithm ]

 

 그리디 알고리즘(greedy algorithm)은 매 단계에서 '가장 좋아보이는' 해답을 선택하는 알고리즘으로 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식입니다. 

 

 즉, 당장 눈 앞에 보이는 최적의 상황만을 쫓는 가장 단순한 형태의 알고리즘입니다. 때문에 욕심쟁이 또는 탐욕 알고리즘이라고 불리기도 합니다.

 

 

★ 그리디 알고리즘을 사용하기 적합한지 판단하는 기준

 

1. 최적 부분 구조(optimal substructure) 속성

 : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우, 문제 P가 최적의 부분 구조를 갖는다고 말합니다. 

 

2. 그리디 선택(greedy choice) 속성

 : 주어진 문제 P에 대한 지역적 최적 솔루션을 반복적으로 선택하여 전체 최적 솔루션을 구할 수 있는 경우, 문제 P가 그리디 선택 속성을 갖는다고 말합니다. 

 

 

 

★ 그리디 알고리즘 vs 동적 계획법

 

 그리디 알고리즘은 빠르게 해를 찾을 수 있다는 장점이 있는 반면, 그 해가 항상 최적의 해라는 보장을 할 수 없습니다. 

 

 동적 계획법은 모든 방법을 일일이 검토하기 때문에 항상 최적의 해를 구할 수 있는 반면, 그만큼 시간이 오래 걸린다는 단점이 있습니다. 

 

그리디 알고리즘	동적 계획법
빠름	느림
항상 최적해 X	항상 최적해 O

 

 다음 그림에서 그리디를 사용하여 최소값을 구할 때의 해와 실제 최적해의 차이점을 볼 수 있습니다.  

 

 

https://iridescent-zeal.tistory.com/16?category=1261295 

[알고리즘]다이나믹 프로그래밍(Dynamic Programming, DP)

 

 

 

 

★ 그리디 알고리즘의 대표적인 문제

 

1. 거스름돈 문제

 

 거슬러줘야 할 돈으 N원일 때, 1000원 500원 100원 50원 10원으로 거슬러 줄 수 있는 경우 중, 화폐의 개수가 가장 적은 경우를 구하는 문제입니다. 

 

 가장 적은 양의 화폐를 건내주는 것이 가장 편하므로 거스름돈 문제에서는 그리디 알고리즘을 통해 큰 단위의 돈부터 생각합니다. 

 

 

2. 최단 작업 우선 스케줄링 shortest-job-first scheduling

 

 은행 창구 대기열에 N명의 사람이 기다리고 있을 때, 이들은 서로 일 처리에 필요한 시간이 다릅니다. 

 

 이때 평균 대기 시간을 줄이기 위해서는 일 처리에 걸리는 시간이 짧은 사람일 수록 먼저 은행 업무를 보게 하면 평균 대기 시간을 줄일 수 있습니다. 

 

 

3. 분할 가능 배낭 문제 factional knapsack problem

 

 가방의 최대 무게가 T를 넘지 않도록 가방에 넣는 물건들의 가격 합이 최대가 되도록 물건을 선택하는 문제입니다. 

 

 '분할이 가능한' 문제이므로 주어진 물건을 원하는 형태로 얼마든지 분할할 수 있고, 각 물건의 일부분만을 배낭에 담을 수 있다고 가정합니다. 

 

 각 물건을 단위 무게당 가격을 기준으로 정렬하고, 그리디 방식에 따라 단위 무게당 가격이 높은 순서로 물건을 선택합니다.