[알고리즘] 그리디 문제 푸는 법

STEP1. 목표가 "최대/최소인가?"

최대 몇 개?
최소 비용?
최소 시간?
최대 이익?

-> 이러한 문제라면 그리디 가능성 염두

 

 

 

STEP2. 선택을 하나씩 해나가는 문제인가?

여러 개 중 하나 선택
-> 다음 선택
-> 다음 선택

-> 그리디 가능성 UP

 

 

 

STEP3. 현재 가장 좋은 선택을 생각해보기

예를 들어 회의실 배정 문제에서: 

회의시간이 짧은 회의?
시작이 빠른 회의?
끝이 빠른 회의?

이렇게 여러 후보를 생각해본다.

 

 

 

STEP4. 이 선택이 미래의 선택 기회를 많이 남기는가?

예를 들어 회의실 배정 문제에서:

빨리 끝날수록 다음 회의를 선택할 기회가 많아진다. 

-> 즉, 종료 시간이 가장 빠른 회의 선택 

 

 

 

STEP5. 반례도 생각해본다. 

가장 빨리 끝나는 걸 골랐더니 오히려 전체 개수가 줄어드는 경우가 있나?

-> 없다면 그디리 알고리즘이 가장 최적의 선택