⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️
1. 그리디(Greedy)란?
그리디 알고리즘이란 "탐욕법"이라고도 부른다. 이 알고리즘은 "현재 상황에서 최적이라고 생각되는 결과값을 선택"하는 알고리즘이다.
장기적(Global)으로 보면 틀린 선택일지라도 현재(Local) 해당 결과값이 최적이라면 해당 값을 선택한다.
즉, 항상 최적해를 보장하는 것은 아니다.
그러면 최적해를 보장하지 않는데 왜 그리디 알고리즘을 쓸까?
계산속도가 매우 빠르다. 같은 내용의 문제를 DP등 다른 알고리즘을 사용하는 것 보다 빠른 속도로 결과값을 도출한다.
게다가 그리디 알고리즘을 활용할 수 있는 문제가 유형화 되어있다. 해당 유형을 익힌다면 그리디 알고리즘을 사용하지 않을 이유가 없다.
2. 그리디(Greedy)을 어떻게 사용할까?
1. 여러가지 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해야 한다. => 선택
2. 선택한 값이 문제의 조건을 만족하는지 확인한다. => 적합성 확인
3. 해결되었다면 종료, 해결되지 않았다면 위의 과정을 반복한다. => 검사
최적인 값을 계속해서 선택해나가는 방식으로 코드를 작성하면 된다.
예를 들어보자.
아르바이트를 하던 중 손님이 가져온 물건의 가격이 3150원이고, 손님이 주신 돈은 5000원이다. 이때 지폐는 모두사용하여 없고 500원, 100원, 50원, 10원짜리 동전만 가지고 있다. 이때 거스름돈으로 동전의 갯수를 최소한으로 거슬러주려면 어떻게 해야할까?
위에 적어둔 풀이 방법을 통해 문제를 해결하면 된다.
1. 선택
거스름돈의 갯수를 줄이기 위해 가장 단위가 큰 동전을 우선 선택한다.
2. 적합성 확인
1번 과정에서 선택한 동전을 몇개 선택할지 정한다.
3. 검사
선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
만약 같다면 그리디 알고리즘을 종료하고, 액수가 부족하다면 1번의 과정부터 반복한다.
결과 => 500원짜리 3개, 100원짜리 3개, 50원짜리 1개
3. 그리디 알고리즘을 사용하면 좋은 유형은?
- Greedy Choice Property : 현재의 선택이 이 후의 선택에 영향을 주지 않는다.
- Optimal Substructure : 매 순간의 최적의 해가 문제 전체의 최적의 해여야 한다.
위 거스름돈 문제에 해당 유형이 적합한지 확인해보자.
- Greedy Choice Property
내가 해당 금액을 거슬러 주고 나서, 다음번 손님에게 거스름돈을 거슬러줄때 영향을 끼치지 않는다.
- Optimal Substructure
가장 높은 단위의 동전을 선택하는 것이 거스름돈을 주는 것에 가장 최적의 해다.
4. Example
-끝-