그리디

본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다.
단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다.

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법
문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다.
정렬 알고리즘과 자주 짝을 이룬다.

거스름돈

그리디 알고리즘의 대표적 예시

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재할 때, 손님에게 거슬러 줄 N원을 위해 줘야 할 동전의 최소 개수는 몇 개일까? (N은 10의 배수)

이 문제는 가장 큰 화폐 단위부터 건내주면 된다

N: 1260

var n = 1260
var count = 0

let coinTypes = [500, 100, 50, 10]

for coin in coinTypes {
    count += n / coin
    n %= coin
}

print(count)

시간복잡도는 동전 타입의 array만큼 for문을 돌기 때문에 $O(K)$ (K는 동전 종류의 개수) 이다.

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수는 없다.
'가장 큰 화폐 단위부터'처럼 기준이 있을 때 효과적이다.

해법이 정당한지 검토해야 한다. 거스름돈 문제의 경우는 큰 단위의 동전이 항상 작은 단위의 배수 이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기에 정당하다.

동전들이 배수 관계가 없을 때는 다이나믹 프로그래밍 방식으로 해결 할 수 있다.

참고

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154