[Swift 이코테] Greedy / 그리디 / 탐욕 알고리즘

그리디 알고리즘이란?

Greedy algorithm은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

한마디로 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로도 최적인 문제들이다.

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스러운 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스러운 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

 

---

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해 준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

그리디를 예시로 들 때 가장 많이 사용되는 예제는 거스름돈 문제이다.

이러한 문제는 가장 큰 화폐의 단위부터 돈을 거슬러 주는 것이다. 

---

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없는 가능성이 다분하다. 하지만 거스름돈 문제에서 가장 큰 화폐 단위부터 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제를 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 굉장히 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 예를 들어 화폐 단위가 500, 400, 100인 경우 800원을 거슬러 줘야 할 때 그리디 알고리즘을 적용하면 500 + 100 + 100 + 100을 거슬러 줘야 한다고 나오는데, 최적의 해는 400 + 400이다. 이 문제에서 큰 단위가 작은 단위의 배수 형태이므로, 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다. 는 아이디어는 정당하다. 대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

---

예시

큰 수의 법칙

N개의 수들 중에 M번 더했을 때 가장 큰 수를 찾는 문제. 연속합은 최대 K번까지 더할 수 있다.

let NMK = readLine()!.split{$0==" "}.map{Int(String($0))!}
var (N, M, K) = (NMK[0], NMK[1], NMK[2])
let input = readLine()!.split{$0==" "}.map{Int(String($0))!}.sorted(by: >)
let oK = K
var sum = 0

while M > 0 {
	while K > 0 {
		sum += input[0]
		K -= 1
		M -= 1
	}
	sum += input[1]
	K = oK
	M -= 1
}

print(sum)