[알고리즘] greedy 알고리즘 (탐욕 알고리즘)

greedy 알고리즘이란

• 매 선택의 순간마다 순간 (local)에 최적인 답을 선택하여 전체 최적해를 구할거라고 기대를 하는 알고리즘이다
• 순간마다의 최적이라고, 그 순간들을 수집한 최종적인 해답이 최적해를 보장하지는 않는다 (하지만 최적해를 보장하는 예는 계산 속도가 엄청 빠르다)

 

-greedy 알고리즘을 적용하기 좋은 조건

→ greedy 알고리즘은 항상 최적해를 보장하지는 않지만 최적해를 보장하는 2가지 조건이 있다

1. 탐욕적 선택 속성: 앞의 최적해 선택이 이후의 최적해 선택에 영향을 주지않는다.즉, 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야 한다.
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

-greedy 알고리즘의 문제 해결 방법

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

 

-대표적인 greedy 알고리즘 문제

• 거스름돈 문제
  • 800원 거스름돈을 낸다고 가정)
  • case1)500원 100 50원 10원 1원 (각 동전이 다른 동전의 배수인 경우) 최적해 보장O -> 500 100 100 100
  • case2)500원 400원 100원 ( 각 동전이 다른 동전의 배수가 아닌 경우) 최적해 보장X -> 500 100 100 100 X 400 400 O
  • case2는 각 동전이 다른 동전의 배수가 아니면 큰 동전이 작은동전을 표현 못하기때문에 큰 동전을 선택했을 때 최적해를 보장 안할 수가 있다.

• 이 문제도 greedy 알고리즘을 적용하지 못하는 예이다.
• 이유는 무엇일까
  • 이유는 루트 노드부터 최적해를 구한다고 가정해보자. 하지만 당장의 최적해를 구한다고 하지만
  • 최적해 이후의 노드 값들에 대해서는 모른다.
  • 그래서 부분 최적해를 구한다고 전체 최적해를 구하지 못하는 예이다.
  • 이 문제는 DP 알고리즘으로 해결해야한다.

 

-greedy 알고리즘의 장단점

• 장점: 계산 속도가 빠르다(DP와 비교했을때)
• 단점: 최적해를 항상 보장하지 않는다(보장하지 않을때는 다른 알고리즘이나 DP 알고리즘을 사용한다)
  • 하지만 최적해를 보장하지 않더라도 근사 알고리즘으로 사용하기도 한다.

 

-greedy 알고리즘 백준 문제 모음집

greedy알고리즘은 다양한 관련 문제를 풀어서 어떤 문제가 greedy알고리즘에 적합할까라는 시각을 기르는 걸 추천합니다.

https://www.acmicpc.net/workbook/view/4380