Greedy 알고리즘

매 선택의 순간마다 당장 눈앞에 보이는 최적의 선택만을 하여 최종적인 답에 도달하는 알고리즘이다.
(이러한 선택의 결과가 항상 최적이라는 보장은 없지만 그리디 알고리즘을 적용하는 문제에서는 최적이 된다.)

예를 들면?

최소 값을 찾아야하는 트리 구조가 있다고 하자

      3
     
   4     2

1    6  5   10

트리가 다음과 같이 생겼을 때
그리디 알고리즘은 3 -> 2-> 5 를 거쳐 5를 최소 값으로 판별한다.

이 예제에서 실제 최소 값은 1이지만, 그리디 알고리즘에서는 당장 눈앞에서 최적의 선택을 한 그 결과가 항상 최적 값으로 보장되기 때문에 이러한 경우는 문제로 나오지 않는다.

백준 11047 - 동전 0

문제 바로가기

풀이

그리디 알고리즘을 사용하는 대표적인 문제이다.
만들어야하는 K원보다 값이 작은 동전 중에서 가장 큰 값을 고르면 되는 문제이다.

최종 코드

import Foundation

let line = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = line[0]
var K = line[1]
var coinArr = Array(repeating: 1000000, count: 10)

for i in 0..<N {
    let coinValue = Int(readLine()!)!
    coinArr[i] = coinValue
}

var count = 0

for i in (0..<N).reversed() {
    let nowCount = K / coinArr[i]
    K -= nowCount * coinArr[i]
    count += nowCount
    
    if K == 0 {
        break
    }
}
print(count)

• 큰 값부터 찾아야하니 reversed()를 사용한다.
• coinArr[i] 값이 K보다 크더라도 nowCount값이 0이 되니 신경쓰지 않아도 된다.