[Algorithm] 그리디(Greedy) 알고리즘

💡 그리디(Greedy) 알고리즘? 

• 최적화 문제를 해결하기 위한 방법이다.
• (입력) 데이터 간의 관계를 고려하지 않고 수행과정에서 현 상황에서 가장 좋은 (locally optimal)을 욕심내어 최소 또는 최대 것을 가진 데이터를 선택하여 문제를 해결
• 전체적으로 최적인지는 판단X, 오로지 현재 최적!
• 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다.
  • 한번 선택하면 절대 번복 X
• 어떤 알고리즘이 항상 global solution을 얻는다는 것을 주장하기 위해서는 논리적인 증명이 필요
  • 증명할 수 없다면, 알고리즘의 해는 suboptimal일 수도 있으며, 이경우 이것을 휴리스틱 알고리즘이라고 부른다

 

그리디 알고리즘으로 해결할 수 있는 문제는?

아래의 두가지 조건이 만족되어야 한다.

1. 탐욕스런 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것을 의미
2. 최적 부분 구조 조건 (or 최적성 원칙) : 문제의 최적해가 부문제들의 최적해로부터 효율적으로 생성

 

 

---

 

➕ 간단한 동전 거스름돈 문제를 살펴보자,,

• 매순간, 남은 거스름돈의 총액을 초과하지 않는 조건하에 가장 큰 액면을 가진 동전을 취함 
• 동전 거스름돈 문제의 최소 동전 수를 찾는 그리디 알고리즘!
  • 단, 동전의 액면은 500원, 50원, 10원, 1원 

🚫 하지만, 이는 항상 최적의 답을 주는 것은 아니다.

• 만약 160원짜리 새로운 동전의 종류가 추가될때,
  • 거스름돈이 200원이라면, 160원 1개, 10원 4개를 리턴한다.
  • 최소동전의 거스름돈은 100원짜리 2개가 된다.

이 그리디 알고리즘으로 거스름돈 교환 문제를 풀게 된다면, 큰 단위의 동전이 작은 단위의 동전의 배수가 되어야 그리디 알고리즘을 적용할 수 있다.

• 160원은 10원, 1원의 배수지만, 50원, 100원의 배수가 되진 않기 때문에 적용 불가능

➰따라서, 탐욕 알고리즘을 사용할 때는 전체적인 최적해 인지를 항상 염두해야한다. 즉, 사용해도 되는지 검증단계를 꼭 거치기!

 

 

---

➰그리디 알고리즘의 적용

1. 최소 신장 트리 (MST) : 크리스컬 알고리즘[O(mlogm)] (m은 그래프의 선분의 수), 프림 알고리즘[O(n^2)]
2. 최단 경로 찾기 : 다익스트라 알고리즘 [O(n^2)]
3. 부분 배낭 문제 [O(nlogn)]
4. 집합 커버 문제 [O(n^3)]
5. 작업 스케쥴링 [O(nlogn)] + O(mn) (n은 작업의 수, m은 기계의 수)
6. 허프만 압축 [O(nlogn)]

 

---

Reference

서울과학기술대학교 컴퓨터공학과 알고리즘 수업