[Algorithm] Greedy(탐욕 알고리즘, 탐욕법)

오늘은 Greedy 알고리즘에 대해 알아보겠습니다.

Greedy의 기본적인 개념은 전체를 고려하지 않고, 현재 상태에서 할 수 있는 최선의 선택을 하는 알고리즘 입니다.

사실 전 처음에 개념의 뜻을 이해하지 못했는데요. 혹시라도 바로 이해가 되지 않더라도 천천히 이해해봅시다.

출처: https://en.wikipedia.org/wiki/Greedy_algorithm

접근법

Greedy를 통해 문제에 접근하는 방식은 다음과 같습니다.

1. 정렬 또는 기준 정의: 해결하려는 문제에 따라 최선에 대한 기준(최대, 최소 등)을 정합니다.

2. 현재 상태에서의 최선을 선택: 각 단계에서 마다 기준에 따른 최선의 선택을 합니다.

핵심

따라서 Greedy를 이용해서 푸는 문제는 대부분 다음과 같은 특징을 갖는 것이 핵심입니다.

- Greedy choice property(탐욕적 선택): 각 단계에서의 항상 탐욕적 선택만 존재합니다.

- Optimal substructure(최적의 하위/하부구조): 문제를 하위(부분) 문제로 나눴을 때, 하위(부분) 문제의 최적해가 전체 문제의 최적해가 됩니다.

활용

주로 최단 경로 문제(Dijkstra Algorithm), Minimum Spanning Tree(MST;Kruskal, PrimA lgorithm), Scheduling 문제, 하위 문제로 나눌 수 있는 배낭 문제(Knapsack) 에 사용됩니다.

Matroid

Matroid(매트로이드)는 특정 문제가 Greedy 알고리즘으로 최적해가 구해진다는 것을 보장하는 수학적인 구조입니다.

Matroid는 두 가지 성질을 만족합니다.

Hereditary Property(or Downward-closed Property; 독립적인 부분 집합)

요소 집합은 독립적이며, 집합의 부분 집합 또한 독립적입니다.

예를 들면 아래 그림에서 상단의 그래프는 부분 집합에 사이클을 갖는 집합(A-D-E-B-...)이 존재합니다.

하지만 아래 두 그래프는 모든 부분 집합들이 사이클을 갖지 않습니다. 이러한 경우를 Minimum Spanning Tree(MST)라고 합니다.

MST는 독립적인 부분 집합의 성질을 잘 나타내는 예시입니다.

 

출처: https://en.wikipedia.org/wiki/Greedy_algorithm

Augmentation Property(or Independent Set Exchange property)

독립적인 집합 두 개가 있을 때 두 집 합 중 하나에서 원소를 하나 빼고, 다른 집합에 원소를 하나 추가해도 두 집합 모두 독립성을 유지합니다.

예를 들면 MST에서 어떤 간선 집합에서 하나의 간선을 빼고, 다른 독립적 집합에서 간선을 하나 추가해도 여전히 사이클이 없는 상태가 유지됩니다.

예제

가장 위의 예제 이미지를 문제로 풀어봅시다.

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

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다.
이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

Input:
- 첫째 줄에 N과 K가 주어진다.
  (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
- 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다.
  (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

문제가 Greedy 알고리즘으로 해결되는 특징을 갖는지 살펴봅시다.

Greedy choice property(탐욕적 선택): 현재 단계(Ai; 동전의 가치)에서 만들어 낼 수 있는 목표치(K)를 넘지 않는 최대값을 선택해야합니다. 따라서 가격이 높은 순서대로 동전을 나열해야한다는 것을 알 수 있습니다.

Optimal substructure(최적의 하위/하부구조): 해당 문제에서의 하위(부분) 문제는 "다음 가격의 동전을 사용하여 남은 금액을 처리하는 방식"입니다. 어떤 동전이라도 모든 단계에서 같은 구조로 작동하며, 이 구조가 전체 문제의 최적해를 구하기도 합니다.

 

이를 코드로 표현하면 아래와 같이 쓸 수 있습니다.

var input = readLine()!.split(separator: " ").map { Int("\($0)")! }
let coins = (0..<input[0]).map { _ in Int(readLine()!)! }
var count = 0
for cost in coins.reversed() {
    if input[1] >= cost {
        count += input[1] / cost
        input[1] %= cost
    }
    if input[1] == 0 { break }
}
print(count)

 

Conclusion

Greedy 알고리즘은 모든 문제에 적용할 수 있는 것이 아닙니다.

따라서 Greedy 문제로 풀 수 있는 문제인지, 아닌지에 대한 빠른 판단이 중요하다고 생각합니다.