L09 - Greedy Algorithms

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

 

Greedy Algorithm 개요

 

Algorithmic Paradigms

 

• Brute-force methods
  
  => 가능한 모든 경우를 살펴보기
  
  
• Divide and conquer
  
  => 문제를 작은 문제로 분할하여 재귀적으로 해결
  
  
• Dynamic programming
  
  => 작은 문제의 결과를 메모해두고 재활용

오늘 다룰 주제는 Greedy algorithms 임!

 

 

Greedy Strategy

 

지금 당장 가장 좋아보이는 것을 선택하는 전략임

 

=> 미래의 상황은 고려하지 않음

Greedy Algorithm 이란 

 

최적해를 항상 보장하지는 않음

현재의 선택이 미래에 미칠 영향을 고려하지 않기 때문에

Local optimum => Global optimum 이 되는게 보장 X

하지만, greedy strategy로 최적해를 찾을 수 있는 문제도 존재!

 

 

Greedy Algorithm이 최적해를 찾기 위한 2가지 조건

 

1. Greedy-choice property

 

=> 현재의 최선의 선택이 최적해에 기여함

 

2. Optimal sub-structure property

 

=> 작은 문제의 정답이 큰 문제의 정답에 포함됨

 

대표적인 Greedy Algorithm 문제들

 

1. 거스름돈 문제

 

https://www.acmicpc.net/problem/5585

 

500원, 100원, 50원, 10원, 5원, 1원 짜리 동전이 충분히 있는 상황에서

 

Greddy strategy로 생각해봤을 때 가치가 큰 동전부터 사용하면 됨

 

1. 남은 잔돈보다 가치가 낮은 동전 중 가장 큰 동전을 사용 (greedy choice)

 

2. 남은 잔돈에서 사용한 동전의 값을 뺌

 

위 과정을 반복하면 된다!

 

Greedy-choice property

거스름돈이 500원보다 크면, 500원 동전을 사용하는 최적해가 반드시 존재함

=> 500원 동전을 안쓰면, 500원을 만들기 위해 더 작은 동전을 많이 사용해야함

Optimal sub-structrue property

거스름돈 x에 대한 최적해 S(x)는 

S(x) = S(x - 500) + 1 if x > 500

 

 

만약 동전이 500, 100, 50, 10 ... 이 아니라 500, 300, 70, 30 ... 이라면?

 

결론은 그리디 알고리즘을 쓸 수 없음

 

왜냐하면 500, 100, 50, 10.. 의 경우 배수의 형태를 띠고 있기에 500원이 더 작은 동전들의 합으로 이루어질 수 있다는게 보장됨
(이 경우 가장 가치가 큰 동전부터 사용하면 최적해가 보장)

 

하지만 500, 300, 70, 30 .. 은 그렇지 않기에 최적해를 보장할 수 없음!

 

예를들면 600원을 받아야 하는 상황에서 그리디를 사용하면

 

500원 + 70원 + 30원으로 총 3개의 동전을 사용하는데

 

최적해의 경우 300원 + 300원으로 총 2개의 동전을 사용하는 것을 볼 수 있음

 

2. 회의실 배정 문제

 

https://www.acmicpc.net/problem/1931

 

가능한 모든 경우를 조사하는 방법은 경우의 수가 2^N 이므로 비현실적임

 

이에 따라 여러 전략을 생각해볼 수 있는데

 

1. 시간이 짧은 회의부터 선택하기

 

시간이 짧은 회의를 선택하면 시간이 겹쳐 1개 밖에 진행하지 못하는 경우가 발생

 

=>  최적해를 보장하지 않음

 

 

2. 회의 시작 시간이 빠른 것부터 선택하기

 

시작시간이 빠르지만 회의 시간이 긴 경우 겹치는 부분이 많음

 

=> 최적해를 보장하지 않음

 

 

3. 회의 종료 시간이 빠른 것부터 선택하기

 

 

 

 

지금까지 선택한 회의와 시간이 겹치지 않는 회의 중 회의 종료 시간이 가장 빠른 회의를 선택

 

=> 최적해 보장

 

Greedy-choice property

종료시간이 가장 빠른 회의를 포함하는 최적해가 반드시 존재

종료 시간이 빠른 순서대로 회의-A, 회의-B .. 라고 가정하면 회의-A를 포함하지 않는 최적해 T가 있다고 가정

=> T에 포함된 회의 중 종료 시간이 가장 빠른 회의가 회의-X라면 T에서 회의-X를 빼고 회의-A를 넣은 해 T'는 최적해임

Optimal sub-structure property

전체 회의 집합이 A이고, 종료시간이 가장 빠른 회의가 a1 = (s1,e1) 이라면 최적해 S(A)는

S(A) = S({ai∈A | si≥e1}) + 1