[알고리즘] Greedy Algorithm

✅ 욕심쟁이 알고리즘 (Greedy Algorithm)

❕ 기본 개념 

- 매 선택마다 현재 시점에서 최적의 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법

- 하지만 그 최적의 답이 최종적인 결과 도출에 대한 최적해를 보장해주지는 않음

- 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 점을 착안하여 고안됨

 

해당 알고리즘이 필요한 문제의 조건은 아래와 같다.

1. 최적 부분 구조

: 부분 문제들의 최적의 답을 이용해서 전체 문제의 최적해를 구할 수 있다.

2. 탐욕적 선택 속성

: 각 단계에서 탐욕스러운 선택을 하는게 전체 문제를 푸는 데 있어서 최선의 선택을 하는 것이라면, 그 문제는 탐욕적 선택 속성을 가지고 있는 것이다.

 

 

❕ 작동 방식 

 

largest path 찾기 - 최적해 아님

 

 

✔ 활용 예시 

- AI 결정 트리 학습법(Decision Tree Learning)

- 최소 신장 트리

- 다익스트라 알고리즘

 

 

✔ 문제 예시 

최적값이 아닌 "되는가"를 확인할 때 또는 "괜찮은 방법"을 찾을 때에 사용할 수 있다.

특히 계산이 정확한 알고리즘에 비해 빠른 경우가 많기 때문에 실용적으로 사용이 가능하다.

 

- 거스름돈 문제: 거스름돈이 N원일 때 거슬러줄 수 있는 동전의 최소 갯수 구하기

- 활동 선택 문제: 시간표 짜기, 회의실 시간 분배

- 제약조건이 많은 대부분의 문제

 

 

참고자료

https://namu.wiki/w/그리디%20알고리즘

https://velog.io/@contea95/탐욕법그리디-알고리즘

https://nulls.co.kr/codeit/399

https://brilliant.org/wiki/greedy-algorithm/