그리디 알고리즘

어떤 문제를 푸는 단계에서 선택의 순간마다 당장의 최적을 선택하여 최종 문제의 최적의 해를 찾아내는 알고리즘이다. 보통의 그리디 문제는 정렬을 수행한 후 문제를 풀면 된다.
Local Optimal Solution = Global Optimal Solution

그리디 알고리즘 사용 조건

• 전 단계의 선택이 다음 단계 선택에 영향을 미치지 않는다.
• 문제에 대한 최적 해가 부분 문제에 대해서도 최적 해이다.

예제 1

• 문제 해석 : 한 강의실에서 겹치지 않게 회의를 최대한 많이 해야한다. 회의를 최대한 많이 하려면 회의가 빨리 끝나야 하므로, 회의를 끝나는 시간을 기준으로 오름차순 정렬하여 빠르게 끝나는 순으로 배치한다.

예제 2

• 문제 해석 : 보트에는 총 두 명까지 탈 수 있다. 그러니, 몸무게를 정렬한 후, 몸무게가 젤 많이 나가는 사람과 젤 적게 나가는 사람을 함께 태우려 해본다. 만약 둘 다 탈 수 있다면 그 둘을 함께 태우면 된다. 만약 둘다 탈 수 없으면 현재 몸무게가 가장 많이 나가는 한 명만 태우면 된다. 이것을 잘 생각해보면 현재 선택할 수 있는 선택지 중 최선이라는 것을 알 수 있다. 만약 둘 다 탈 수 있는데 가장 가벼운 인간을 태우지 않고, 다음 인간을 태운다 생각하면, 이는 최선이 아니다. 그리고 만약 둘 다 탈 수 없으면, 현재 가장 가벼운 인간보다 더 무거운 인간은 당연히 같이 태울 수 없으므로 가장 무거운 사람 혼자 태우는 것이 최적이다.