[알고리즘 / 백준 / Swift] 탐욕법 Greedy - 백준 5585 번

이 포스트는 활동하는 동아리 내에서 공부한 뒤, 작성하였습니다.

일반적으로 프로그램은 구현에서부터 시작합니다.

단순한 구현은 높은 시간 복잡도를 초래할 수 있습니다. 조건문과 반복문은 재귀 호출을 이용하기에 때문이겠죠?

즉, 거대한 데이터에서 빠르게 정답을 도출해야 되는 구현 알고리즘의 상황과는 맞지 않습니다.

 

그리하여 탐욕법이라는 알고리즘을 사용합니다.

우리는 거대한 데이터 크기에서 빠르게 정답 도출을 위해 그 순간마다 가장 최적의 해를 빠르게 구해야 합니다.

이는 정확도는 보장이 안 되지만 빠른 시간 복잡도를 가집니다!

 

Greedy 알고리즘은 정확히 무엇일까요?

이 알고리즘은 어떠한 정해진 알고리즘 규격이 아닙니다. 매 순간마다 가장 최적의 해를 도출할 수 있는지가 중요한 것입니다.

또한, 자신이 생각했을 때 탐욕법으로 해결할 수 있을지 그렇게 하더라도 최적의 해를 보장한다는 정당성을 가질 수 있는지 빠르게 도출해내는 능력이 필요하게 됩니다.

 

문제 풀이를 통해 알아 보겠습니다.

 

---

문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

 

입력

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

 

출력

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

 

예제 입력 1

380

 

예제 출력 1

4

 

예제 입력 2

1

 

예제 출력 2

15

 

문제 풀이

var n = 1000 - Int(readLine()!)!
let money = [500, 100, 50, 10, 5, 1]
var ans = 0
// 지폐를 내림차순으로 순회하면서
for m in money {
    // 지폐로 전체 돈을 나눈 몫은 정답에 더하고
    ans += n / m
    // 나머지는 n 에 할당하여 다음 연산을 수행
    n %= m
}

print(ans)

 

배열을 정렬하는 것이 위 문제를 풀 때 중요한 포인트가 될 것 같습니다.