[CS지식 - 알고리즘] 탐욕 알고리즘

1. 탐욕 알고리즘(Greedy Algorithm)

• 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 탐욕 알고리즘은 최적해를 구하는데 사용되는 근사적인 방법
• 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달
  ▶그 순간에서 가장 좋은 것을 고르는 행위가 그 문제의 모든 경우의 수에서 발생하는 최적의 해라는 것을 담보하지 않음
  ▶ 탐욕 알고리즘을 적용 할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제이다

 

1-1. 탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차 : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정 반복

1-2. 문제를 탐욕 알고리즘으로 풀기 위한 조건

1. 탐욕적 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않음
2. 최적 부분 구조 조건 : 문제에 대한 최적해가 부분문제애 대해서도 역시 최적해

 

관련 문제

백준 11047번

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

참고)

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

https://chongmin-k.tistory.com/entry/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%83%90%EC%9A%95%EB%B2%95

그리디 알고리즘(탐욕법)