탐욕 알고리즘(Greedy Algorithm)

모든 선택에서 현재 당장 최적인 답("부분 최적해")을 선택해 최종 결과를 도출하는 알고리즘이다. 백트래킹을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능한 경우는 검증하지 않는다. 

 

그리디 알고리즘의 한계는 각 단계에서는 최적이었을 수 있으나 결과론적으로 전체의 최적이 되지 않을 수 있다는 것!

 

그럼에도 그리디 알고리즘을 사용하는 이유는 속도가 빠르기 때문이며 어느 정도 최적 해에 근사한 값을 구할 수 있기 때문이다. 그리디 알고리즘을 사용해서 답을 도출할 수 있으려면 탐욕 선택 속성(이전의 선택이 이후에 영향을 주지 않음)과 최적 부분 구조(부분 문제의 최적 결과가 전체에도 그대로 적용)를 충족해야 한다.

 

1) 거스름돈 문제(동전 개수 최소 구하기; 단, 각각의 거스름 돈의 서로의 배수/약수 관계일 때만 성립) 

2) 부분 배낭 문제

 

 

빈출유형

최소 신장 트리 구하기: 프림, 크루스칼, 다익스트라