chapter 3. 그리디

 그리디는 탐욕적이라는 뜻으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미합니다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.

이 책에서는 그리디 알고리즘은 다른 알고리즘과 비교해서 비교적 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라고 소개 해고 있습니다. 하지만 다익스트라 같은 알고리즘도 최단거리 이면서 그리디로 분류 되므로 무조건적이지는 않습니다. 몇가지 감만 익히면 그리디 알고리즘을 코딩테스트에서 틀릴 일을 없다고 생각이 듭니다.

 

제가 이 책으로 공부하면서 얻은 그리디 문제 풀이 방법에 대한 팁은 최소한의 문제에 대한 아이디어를 떠올리고 그리디적 사고가 타당한지를 스스로 검증하는 것입니다. 그리고 바로 그리디 적용해버리는 것이지요. 여기서 list에 대한 메소드  sort(), reverse(), min(), max() 등을 외우면 더욱 간단히 풀이가 가능해진듯 합니다. 

 

풀이 :

https://github.com/10000sukk/Algorithm/tree/master/python-for-coding%20test