Greedy : 가장 좋은 것을 선택해라!

 - 이름에서 알 수 있듯이 Greedy는 단순, 무식하게 탐욕적으로 푸는 알고리즘이다.

하지만 단순, 무식하게 푼다는것은 생각보다 쉽지 않다.

여기서 무식하게 푼다는 의미는

예를 들어 우리가 여러 지폐들중 하나만 가질 수 있다고 한다면, (무조건 한 장만 가능하다.)

가장 값어치가 가장 큰 지폐를 선택하게 된다. 이것은 어쩔 수 없다. 

이런게 그리디인데

코딩 테스트에서는 단순하게 문제가 나오지는 않는다.

그리디가 사전에 외우지 않고 있어도 풀 수 있는 가능성이 높은 유형이라고는 하지만,

다른 유형과 함께 등장하는 경우도 많다고 한다.

예를 들어, 정렬알고리즘과 함께 사용하던가,

최단경로를 구하는 알고리즘과 함께 사용한다고 할때  이들을 미리 알고 있지 않으면 문제를 풀지 못하는 상황이 발생할지도 모른다.

 코팅테스트에서는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 팍악해야만 한다.

- 이것이 코딩테스트다

 

모든 그리디 문제가 그러는지는 모르겠지만, 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로,

문제에서 가장 큰 순서대로, 가장 작은 순서대로등

순서와 관련된 내용을 함축하고 있다면 그리디일 확률이 높다고 한다.

때때로 정렬 알고리즘과 짝을 이뤄가며 출제 된다.