그리디 알고리즘 이란?
탐욕의 알고리즘 또는 욕심쟁이 알고리즘이라고도 하며 현재 상황에서 가장 좋은 것을 선택하는 알고리즘을 말한다. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이며, 이렇게 선택한 것이 최선이길 바라는 알고리즘이다!
그리디 알고리즘은 동적 프로그래밍 사용시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 그렇지만 동적 프로그래밍을 대체하는 것은 아니고 보완하는 개념으로 쓰인다.
그리디 알고리즘 문제점
그리디 알고리즘이 모든 경우에서 통하지는 않는다. 예를 들어 마시멜로 실험에 비유를 한다면 지금 당장 1개의 마시멜로를 얻을 수 있지만 기다린다면 2개를 먹을 수 있다. 하지만 그리디 알고리즘은 지금 당장 최적인 답을 선택 하기 때문에 1개의 마시멜로를 선택하게 된다.
즉, 그리디 알고리즘은 전체에서 언제나 최적값을 구할 수는 없다는 것이다!
그리디 알고리즘 동작 조건
그리디 알고리즘을 사용하기 위해선 2가지 조건이 필요하다.
1. 탐욕 선택 속성
- 탐욕적인 선택이 항상 안전하다는 것을 보장해야 한다. 여기서 안전하다라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.
즉, 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적 선택으로 전체 문제의 최적해를 반드시 구할 수 있다는 것을 보여야한다.
- 최적 부분 구조
- 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있다는 것을 보장해야 한다.
즉, 문제에 대한 최종 해결 방법이 문제에 대해서도 최적의 해결 방법이다는 조건을 보여줘야한다.
그리디 알고리즘이 필요한 상황
그렇다면 그리디 알고리즘이 필요한 상황은 언제일까?
시간표 짜기, 거스름돈 계산, 회의 시간 분배 같은 활동 선택 문제 유형에 그리디 알고리즘으로 풀 수 있다.
ex) 거스름돈 예시
거스름돈으로 사용할 500원, 100원 50원, 10원짜리 동전이 주어진다. 손님에게 거슬러줄 돈 N원이 주어질 때 주어야할 동전의 최소 개수를 구하시오.
500원 1개와 100원 5개를 비교하면 큰 단위의 동전부터 나누는것이 효과적임을 알 수 있다.
1,580원으로 예를 든다면
으로 계산 할 수 있다.
참고 사이트
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://hevton.tistory.com/364
https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
