탐욕알고리즘은 발견법(heuristic method)의 방법중 하나.
발견법(heuristic method)
- 최선, 최적의 답을 찾기보다도 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론
- backtracking(역추적)과 같이 알고리즘 수행시간이 많이 걸릴 때 사용하는 방법 (역추적과 구조는 비슷하지만 방법이 다름)
- 탐욕법은 이전의 선택으로 돌아가는 역추적과는 반대개념으로, 다른 문제들과 독립적이다
탐욕법이 쓰이는 실제상황예시
1) 여행짐싸기(물건담기) :
- 여행 배낭에 물건을 정해진 시간 내에 담으려는 경우, 우선순위가 높은 순서대로 물건을 담을 때 한번 배낭에 담은 물건은 다시 빼지 않는다.
2) 여행경로 짜기(도시방문) :
- 도시가 많아질 수록, 도시를 방문(배열)할 수 있는 가짓수가 많아진다.
- 알고리즘 연산 비용도 함께 증가한다. 이러한 상황에서 탐욕 알고리즘을 활용한다.
- 1) 방문하지 않은 도시 중 가장 가까운 도시로 간다.
- 2) 모든 도시를 방문할 때까지 반복한다.
3) 전력망 연결(전력공급) :
- 발전소 한 개로 여러 마을에 전력을 공급하는 경우, 최소비용을 들여서 모든 마을에 전력을 공급하려면 어떻게 해야 하는가?
- 1) 전력이 공급되지 않은 마을과 공급되는 마을의 사이가 가장 가까운 것을 골라, 두 마을을 연결한다.
- 2) 모든 마을에 전력이 공급될 때까지 반복한다
DP와 Greedy의 차이점
최적 부분 구조 문제를 푼다는 점에서 비교된다.
- DP
- 중복되는 서브문제
- 문제를 작은 단위로 분할하여 해결한 후, 해결된 중복문제들의 결과를 기반으로 전체문제를 해결한다.
- Greedy
- 중복되지 않는 서브문제
- 각 단계마다 최적해를 찾는 문제로 접근한다
- 해결해야 할 전체문제의 갯수를 줄이기위해 개별적으로 문제를 해결해나가는 선택을 한다.
탐욕알고리즘 의사코드
# 탐욕 알고리즘에 대해 의사코드로 이해해보자.
def greedy(items, max_weight):
bag_weight = 0 # 정해진 가방무게
bag_items = list() # 가방에 담을 물건들을 리스트에 담는다.
for each_item in sort_by_value(items): # 각각의 물건을 우선순위에 맞게 담기 위한 반복작업
if max_weight >= bag_weight + item.weight: # 가방무게가 꽉차기 전까지 물건의 무게와 비교한다.
bag_weight = bag_weight + item.weight # 가방에 물건이 담길 때마다 가방의 무게가 찬다.
bag_items.append(item) # 가방에 물건이 담긴다.
return bag_items # 가방의 물건이 무엇이 담겼는지 확인한다.
