그리디(Greedy) 알고리즘

  • '탐욕적으로' 문제를 풀어나간다
    → 현재 상황에서 지금 당장 좋은 것만 고르는 방법
  • 매 순간 가장 좋아 보이는 것을 선택하며, 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘 기준

  • 문제에 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 제시
  • 이러한 기준 때문에 정렬 알고리즘 과 짝을 이뤄 출제

예제: 거스름돈

문제

카운터에서 거스름 돈으로 사용할 500원, 100원, 50원, 10원짜리 동전들이 무제한으로 있을 때
거스름돈 N원을 동전의 갯수를 최소한으로 사용하여 가글러 준다.
(단, 거스름돈 N은 10의 배수)

'큰 화폐 단위부터' 돈 거슬러 주기

  • 제일 큰 단위인 500원으로 거슬러 줄 수 있을 만큼 거슬러 준 뒤, 100원, 50원, 10원 순서로 거슬러 준다.

  • 예시: 2,670원을 거슬러 준다고 하면

    • 500원: 5개
    • 100원: 1개
    • 50원: 1개
    • 10원: 2개

코드 예시

import Foundation

func coinCountMin(_ change: Int) {

    var money = change
    let coin_list = [500, 100, 50, 10]
    var coinCount = 0

    for coin in coin_list{
        let count = money / coin
        if count != 0 {
            coinCount += count
            money -= coin * count
        } else { continue }
    }

    print(coinCount)
}

coinCountMin(1260)

코드 특징

  • for coin in coin_list 구문에서 알 수 있듯이, 화폐의 종류만큼 반복 수행이 필요하다.
  • 따라서, 동전의 종류가 N개일 때, 코드의 시간 복잡도는 O(N)이 성립된다.
  • 이를 통해 거스름돈이 아닌, 동전의 종류만 알고리즘의 시간 복잡도에 영향을 주는 것을 알 수 있다.

그리디 알고리즘의 정당성

  • 대부분의 문제는 그리디 알고리즘을 이용했을 시 '최적의 해'를 찾지 못할 수 있다.
  • 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.

그리디 알고리즘의 적용 불가 예시

"현재 돈통에는 500, 400, 100원이 무수히 있으며, 800원을 거슬러 줄 경우 동전을 가장 적게 주도록 한다."

  • 그리디 알고리즘 방식
    - 500원: 1개
    - 100원: 3개

  • 실제 최적해
    - 400원: 2개

실제 최적해가 그리디 알고리즘의 해에서 절반으로 줄어든 것을 알 수 있다.

알고리즘 적용 조건

맨 처음 예제에서 500원, 100원, 50원, 10원이듯이 각 단위들이 서로 배수 형태로 이뤄져야 한다.

0개의 댓글