[Algorithm] 그리디 알고리즘 (Greedy Algorithm), 탐욕법

 

 

Greedy Algorithm (그리디 알고리즘)

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

 

 

그리디 알고리즘의 특징

- 그리디 알고리즘 유형 문제는 매우 다양하기 때문에 많은 유형을 풀어봐야 한다!

- 현재 상황에서 가장 좋은 것만 선택해도 문제가 해결되는지 파악한 후, 적용한다

 

- 보통 코딩 테스트에서 문제를 풀기 위한 최소 아이디어를 떠올릴 능력을 요구하는 문제이다

    * 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로' 같은 기준을 알게 모르게 제시한다

    * 자주 정렬 알고리즘(기준을 만족시킬 수 있음)과 짝을 이뤄 출제

 

 

 

그리디 알고리즘의 정당성

- 정확한 답을 구할 수 있다는 보장이 있을 때, 매우 효과적이고 직관적인 알고리즘이다

- 그 해법이 정당한지 검토할 수 있어야 한다

 

 

 

간단한 예제

- [문제] 500, 100, 50, 10원짜리 동전으로 N원을 줄 때, 동전의 최소 개수

- '가장 큰 화폐 단위부터' 돈을 거슬러준다 (500 -> 100 -> 50 -> 10)

- 동전의 단위가 서로 배수 형태

 

- 화폐의 단위가 무작위일 경우, 다이나믹 프로그래밍으로 해결 가능하다

 

 

 

 

 

 

📚 참고서적 : 이것이 코딩테스트다 with 파이썬