[이코테] ch3. 당장 좋은 것만 선택하는 그리디

Ch3. 당장 좋은 것만 선택하는 그리디

단순하지만 강력한 문제 해결 방법, 현재 상황에서 지금 당장 좋은 것만 고르는 방법

보통 코딩 테스트에서 출제되는 그리디 알고리즘의 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘의 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됨.


그리디 알고리즘으로 문제의 해법을 찾았을 때에는 그 해법이 정당한지 검토해야 한다.


실제 거스름돈 문제에서 동전의 단위가 서로 배수 형태가 아니면, 그리디 알고리즘으로는 해결할 수 없다.