Greedy Algorithm

Greedy

탐욕스러운, 욕심이 많은

Greedy Algorithm

• 문제 해결 과정에서 결정 순간마다 눈앞에 보이는 최선의 선택을 함
• 선택을 번복하지 않음
• 지역 최적해를 추구함
• 부분적으로는 최적해를 구한다고 할 수 있지만 전체적으로도 최적해를 구했다고는 장담할 수 없음
• 빠른 시간 내에 근사해를 제공

거스름돈 내어주기

8원을 거슬러 줄 때, 동전 종류가 5, 4, 1원만 있는 상황에서 동전 개수를 가장 적게 만듦

• 그리디 알고리즘 사용 : 가장 큰 동전부터 거슬러줌 -> 5원, 1원, 1원, 1원(4개)
• 실제 가장 적은 동전 개수 : 4원, 4원(2개)

Greedy Algorithm이 최적해를 보장하는 경우

• Optimal substructure(최적 부분 구조) : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
• Greedy selection property(그리디 선택 속성) : 선택 과정이 다른 과정에 영향을 주지 않음

Activity Selection Problem(활동 선택 문제)

• 하나의 활동을 완료하기 전까지는 다른 활동을 선택할 수 없음 -> 하나의 활동은 선택하지 않은 나머지 겹치지 않은 활동에 대하여 독립적임
• '이전 선택의 종료 시간'과 '이후 선택의 시작 시간'이 겹치지 않아야 함
• 최대한 많은 활동을 하기 위해서는 종료 시간이 빨라야 함
• 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 것
• 시작 시간을 기준으로 문제를 풀면 종료 시간을 한번 더 고려해야되기 때문에(시작한 시간을 기준으로 선택할 활동이 다음 활동의 시작 시간보다 같거나 작은지 확인) 종료 시간을 기준으로 정렬하는 것이 더 직관적이고 효율적임

주어진 값

종료 시간을 기준으로 정렬

종료 시간이 빠른 것 선택

출처