탐욕법

Chapter 3. 그리디

그리디 알고리즘(Greedy Algorithm) 당장 좋은 것만 선택하는 방법을 그리디(탐욕법) 알고리즘이라고 하며 단순하지만 강력한 문제 해결 방법이다. 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만을 고르는 방법'을 의미한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 이는 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다.(정렬, 최단 경로 등의 알고리즘 유형의 경우 미리 알고리즘 사용 방법을 숙지하고 있어야 해결 가능한 경우가 많다.) 그리디 알고리즘 자체가 문제 출제 폭이 매우 넓기 때문에 최단 경로 알고리즘에 속하는 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘이므로 그리디 알고리즘이면서도 '암기'가 필요한 알고리즘도 있을 수 있..