[Algorithm] 탐욕 알고리즘 (Greedy algorithm)

이번 정리는 그리디 또는 탐욕 알고리즘에 관한 것이다. 사전에 알고리즘을 외우지 않아도 된다는 특징을 가지고 있다.

그리디 알고리즘

• 현재 상황에 지금 당장 좋은 것을 선택하는 알고리즘

• 특정 기준에 따라 좋은 것을 선택하하는 알고리즘이므로,,순서에 관련된 기준이 문제에서 제시된다.

• 따라서 정렬과 같이 나오는 경우가 굉장히 높다.

문제풀이 전략

• 그리디 알고리즘을 이용하기 위해서는, 현재의 선택이 언제나 최적해인지 판단해야 한다.

• 단순한 최소 경로 문제처럼, 각 단계에서의 최적 선택의 합이 전체 단계의 최적 선택일 때 이 알고리즘을 사용해야 한다.

• 문제에서 기준이 반드시 제공되므로, 그 기준에 따라 풀되 edge case 발생시 과감하게 그리디적 접근을 포기한다.

예시문제

백준 11047 동전0

백준 1789 수들의 합

백준 1931 회의실 배정