이것이 코딩 테스트다 :: 그리디

단순하지만 강력한 문제 해결 방법이다. 

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘으로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘과 자주 짝을 이뤄 출제된다. 

 

탐욕적인 해결법이 존재하는지 고민해보자. 해결 방법을 찾을 수 없다면, 이후의 장에서 다루게 될 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지를 재차 고민해보는 것도 한 방법이다.

 

문제풀이