[이론] 탐욕적(그리디) 알고리즘

1. 탐욕적(Greedy) 알고리즘이란?

Greedy는 “탐욕스러운, 욕심 많은”이란 뜻을 가진 용어로, 바로 눈앞의 이익만 쫓는 알고리즘을 말합니다.

최적화 문제를 대상으로 하며, 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼습니다. 

 

2. 그리디 알고리즘의 2가지 조건

• 탐욕 선택 속성
  탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말합니다. 즉, 선택을 다시 고려하지 않습니다.
• 최적 부분 구조
  최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말합니다.

 

3. 그리디 vs 다이나믹 프로그래밍(DP)

두 알고리즘은 흔히 비교되는데, 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다릅니다.

그리디	DP
각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태	하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 함

 

4. 탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

 

5. 그리디로 풀 수 있는 문제

조합 최적화에서 매우 유명한 예시인 배낭 문제가 있습니다.

배낭 문제
배낭에 담을 수 있는 무게의 최댓값(15kg)이 정해져있고 각각 짐의 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 하는 문제입니다. 즉, 가치가 최대가 되도록 짐을 고르는 방법을 찾는 문제입니다.

이 문제는 그리디와 DP 모두로 해결이 가능합니다.

그림과 같이 있을 때 각 짐의 단가를 구하고 높은 단가순으로 정렬한 뒤 가방 용량에 맞게 담으면 해결이 가능합니다. 예시에서는 C의 단가가 2.5달러로 가장 높으므로, C, B, E, D 순으로 8kg의 짐을 담고 남은 7kg는 A의 7/12만큼 쪼개서 배당에 담는 것이 최적해입니다.

 

 

6. 그리디로 풀 수 없는 문제

그리디 알고리즘의 실패 사례로는 가장 큰 합 문제가 있습니다.

각 노드에서 매번 가장 큰 수를 선택하면  7 → 12 → 6으로 선택할 수 있습니다. 하지만 실제 가장 큰 합의 결과는 109(7 → 3 → 99)가 정답이 됩니다. 그리디 알고리즘에서는 99를 발견할 수 없습니다. 이 문제는 이진 트리를 정렬하든지 등의 추가 작업없이 그리디 알고리즘으로 풀이할 수 없습니다.

 

 

 

참고자료 : 

- 파이썬 알고리즘 인터뷰