1. 그리디 알고리즘이란?

그리디 알고리즘 즉, 탐욕 알고리즘이란 "매 선택에서 당장 최적인 답을 선택하여 적합한 결과를 도출하는 방법" 이라고 설명할 수 있습니다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 때에는 최적이라는 보장은 절대 없다는 것을 명심해야합니다.

예를 들자면 마시멜로 실험에 비유할 수 있습니다. 당장은 눈 앞에 1개의 마시멜로를 먹는게 이득이지만, "기다렸다가 2개를 먹는다" 라는 최적해를 보장하지 못합니다.

2. 어떤 경우에 사용할까

탐욕 선택 속성, 최적 부분 구조 특성을 가지는 문제들을 해결하는 데 강점이 있다.
즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

(출처 - 나무위키)

위 그럼처럼 한 번의 선택이 다음 선택에 영향을 미치지 않는 상황에서 그리디 알고리즘이 최적해를 구해줄 수 있다. 이러한 구조를 최적 부분 구조라고 한다.

3. 그리디 알고리즘 문제를 해결하는 방법

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

4. 예시

• 거스름돈 문제
• 최소 신장트리
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘

5. 실패하는 경우

대표적으로 배낭 문제(Knapsack Problem)이 있다.

6. Swift를 통해 풀어보기 with. 동전문제

백준 - 동전문제를 예시로 풀어보겠습니다.

1. 선택 절차

동전의 개수를 최소한으로 만들기 위해 가치가 가장 큰 동전부터 선택합니다.

2. 적절성 검사

1번 과정에서 선택한 동전이 남은 가격을 넘는지 확인합니다.
초과를 한다면 가격이 다음으로 큰 동전을 선택합니다.

3. 해답 검사

원하는 금액이 남았는지 확인하고, 액수가 남아있다면 1번으로 다시 갑니다.

코드

let input: [Int] = (readLine() ?? "").split(separator: " ").map{ Int($0) ?? 0 }
var (n, k): (Int, Int) = (input[0], input[1])
var coinArray: [Int] = []
var index: Int = 0
var result: Int = 0

for _ in 0..<n {
    let coinInput = Int(readLine() ?? "") ?? 0
    coinArray.append(coinInput)
}

coinArray.reverse()

while k > 0 {
    if k >= coinArray[index] {
        k -= coinArray[index]
        result += 1
    } else {
        index += 1
    }
}

print(result)