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

그리디 알고리즘에 대해 알아보고 대표문제를 Swift로 한 번 풀어보겠습니다.

그리디 알고리즘이란?

그리디 알고리즘을 번역하면 탐욕 알고리즘 이라고 한다.

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

즉, 매 순간마다 최선의 경우를 고르고 다른 경우는 고려하지 않는다.

그리디 알고리즘의 어려운 점은 이 문제가 그리디가 맞는지 판별하는 것이 가장 어려운 것 같다.

계속해서 반례가 있는지 확인해야하고 고민해야 한다.

그리디 알고리즘은 정렬 알고리즘과 주로 짝을 이루기도 한다.

대표 문제

1. 백준 5585 거스름돈

5585번: 거스름돈

let coins = [500, 100, 50, 10, 5, 1]
var changes = 1000 - Int(readLine()!)!
var count = 0

coins.forEach {
    count += changes / $0
    changes %= $0
}
print(count)

2. 백준 11047 동전 0

11047번: 동전 0

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0]
var k = input[1]
var coins: [Int] = []
var count = 0

for _ in 0..<n {
    coins.append(Int(readLine()!)!)
}

coins.sorted(by: >).forEach {
    count += k / $0
    k %= $0
}

print(count)

위 두 문제는 어째서 그리디 알고리즘일까?

동전들 중에서 항상 큰 단위의 동전이 작은 단위의 동전의 배수이기 때문이다.

예를들어서 동전의 단위가 70원, 60원, 10원이고, 거슬러줘야 할 돈이 120원이라고 가정해보자.

그리디로 접근하게 된다면 (70 + 10 + 10 + 10 + 10 + 10) 총 6개의 동전을 거슬러줘야하는 게 최소값이다.

하지만 최적의 해는 (60 + 60)으로 2개이다.

이러한 것 때문에 그리디가 어렵다.

항상 반례가 있는지 확인하고 그리디 알고리즘이 맞는지 확인해야한다.

두 문제와 비슷하지만 다른 문제가 있다.

2293번: 동전 1

이 문제는 동전이 배수다. 이러한 말이 없으므로 그리디로 풀 수 없다.

그리디 문제로 해결할 수 없다면, 다른 알고리즘을 떠올려보도록 하자. 위 문제는 다이나믹 프로그래밍으로 해결할 수 있다.