03_그리디알고리즘

★ 그리디 알고리즘

- 최적화 문제를 해결하는 알고리즘

- 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림

 

 

 

ㅇ 최적화 (optimization) 문제

- 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제

 

 

ㅇ 특징

- 데이터 간의 관계를 고려하지 않고 수행 과정에서 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택

(‘근시안적’인 선택)

- 일단 한 번 선택하면, 이를 절대로 번복하지 않음

  -> 매우 단순하며, 또한 제한적인 문제들만 해결 가능

 

 

 

 

★ 예시1. 동전 거스름돈 문제

- 남은 액수를 초과하지 않는 조건하에 ‘욕심내어’ 가장 큰 액면의 동전을 취하는 것

 

 

ㅇ 알고리즘

 

-> CoinChange 알고리즘은 항상 최적의 답을 주지 못함

(따라서 실제로는 거스름돈에 대한 그리디 알고리즘이 적용되도록 동전이 발행됨)

 

 

 

 

★ 예시2. 최소 신장 트리

- 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리