[ Do it! 알고리즘 코딩 테스트 ] 그리디 알고리즘

 

[ Algorithm ] 그리디 알고리즘

 

이전에 그리디 알고리즘을 공부하면서 정리한 내용이다. 또 코딩테스트 때 자주나오는 알고리즘의 하나이다.

 

🔷 그리디(Greedy) ?

: 탐욕법이라고도 불리며, 현재 상태에서 보는 선택지 중 제일 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 즉 눈 앞의 가장 큰 이익을 추구하는 기법이다. 

 

대부분의 그리디 문제에는 일반적으로 "최대한 적은, 최대한 많은" 이라는 문구가 문제에 들어가는 경우가 많다. 즉 최대/최소의 경우의 수를 구할 것의 요구하는 문제들을 이야기 할 수 있다.

 

🔷 그리디 특징

  ◾ 최대한 적은, 최대한 많은 이라는 문구가 들어가 있는 문제

  ◾ 최대, 최소의 경우의 수를 구할 것을 요구하는 문제

  ◾ 그리디를 사용할 수 있는 조건이 주어짐

  ◾ 정렬을 한 뒤 이용해서 푸는 문제가 많음

 

🔷 관련 문제