[고급 알고리즘] Greedy

1. Greedy 란?

• 매 순간 가장 좋은 선택을 하는 알고리즘 입니다.
• 근시안적인 방식으로 최적해를 구합니다.

 

목적

• 많은 연산이 필요한 Dynamic Programming의 효율적인 대안으로 사용하기 위함입니다.
• 사용조건을 만족하면, Dynamic Programming보다 더 효율적으로 해를 구할 수 있습니다.

 

동작 방식

• 각 단계에서 최적의 답을 선택하므로써 전체적인 최적해를 구하는 방식으로 동작합니다.

 

사용 조건

탐욕적 선택 속성 (greedy choice property)

• 각 단계에서의 선택이 전체 해결책의 최적성을 보장
• 현재 선택이 문제의 나머지 부분에 독립적 (문제의 남은 부분에 대한 탐욕적 기준 유지)

 

최적 부분 구조 (optimal substructure)

• 문제의 최적해는 전체 문제의 부분문제의 해로 구성됩니다.
• 작은 문제로 나누어 해결하고, 이 해결책들을 결합함으로써 전체 문제의 해를 얻을 수 있음을 의미합니다.

 

2. 대표 문제

거스름돈 문제

주어진 단위의 수에서 최소 개수만 사용하기

 

• 최소 동전 개수로 거스름돈을 주는 문제입니다.

 

해결 방법

• 가장 큰 단위의 동전부터 최대한 사용하여 거스름돈을 줍니다.

 

탐욕적 선택 조건

• 현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.
• 우선적으로 큰 단위의 동전을 최대 사용하면, 전체적으로 사용되는 동전의 수를 최소화 할 수 있습니다.

 

최적 부분 구조

• 큰 단위의 동전을 사용한 후, 남은 거스름돈에 대해서도 동일한 방식을 적용할 수 있습니다.

 

반례

• 작은단위는 큰 단위의 배수여야 합니다.
• 작은 단위의 동전들을 조합했을 때, 전체 거스름돈 갯수가 더 적어지는 경우가 발생할 수 있습니다.
• 6원, {1, 3, 4}

 

Minimum Spanning Tree - 간선 연결 문제 

• 주어진 점들을 모두 연결하는데 필요한 최소한의 간선과 비용을 찾는 문제입니다.

 

해결방법

• 모든 점이 연결될 때까지 가장 가까운 점들을 연결합니다.

 

Job Scheduling

• 여러 개의 작업이 주어지고, 각 작업은 보상과 데드라인이 있음
• 작업을 조합해서 총 이익이 가장 크도록 하기

 

해결방법

• 보상 기준으로 내림차순 정렬
• 각 작업을 최대한 데드라인 근처에서 배정
  • 이미 다른 작업이 배정되었다면, 가능한 더 앞쪽의 시간에 배정
  • 작업을 배정할 수 없으면, 작업 건너뜀

 

Fractional Knapsack

• 물건을 일부 쪼개서 배낭에 넣을 수 있는 상황
• 배낭에 물건을 최대의 가치로 넣기

 

해결 방법

• 가치 대비 무게 비율을 기준으로 높은 순서대로 물건 넣기

 

 

출처

• Wiki - Greedy Algorithm
• Wiki - Activity Selection Problem
• Wiki - Minimum spanning tree
• BaaaaaaaarkingDog - Greedy