🧩 Problem Solving/[알고리즘 for PS]

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm) 탐욕법으로도 알려진 문제 해결 방법이다. 이름 그대로 주어진 문제를 단순하게 탐욕적으로 푸는 알고리즘이다. 탐욕적이라는 말은 '현재 상황에서 가장 좋은 것만 계속 고르는 방법'을 말한다. 그리디 방법음 알고리즘의 각 단계에서 그 순간에 최적이라고 생각하는 것을 선택한다. 또한 그리디로 문제를 해결할때는 현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 사용할 수 있다. 우리는 그리드 문제를 풀 때는 다익스트라(dijkstra) 또는 위상 정렬(topological sort) 알고리즘처럼 특정 알고리즘 코드를 미리 알 필요는 없다. 대신 우리는 문제를 봤을 때 '그 문제가 그리드 알고리즘으로 해결할 수 있는지'에 대해 알아야 한다. 그럼 어떻게 알 수 있..