[Algorithm] 그리디(Greedy) 알고리즘 - Python, Kotlin

모든 내용은 이것이 취업을 위한 코딩테스트다(나동빈 저)의 내용을 정리한 것입니다.

그리디(Greedy) 알고리즘

'탐욕' 알고리즘

→ 현재 상황에서 지금 당장 좋은 것만 고르는 방법

∴ 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않음

 

이 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해줌

→ 이 기준은 정렬 알고리즘을 사용했을 때 만족할 수 있으므로 그리디는 정렬 알고리즘과 자주 함께 나온다!

 

[ 알고리즘 순서 ]

1. 해 선택(Selection Procedure) : 지금 당장의 최적의 해를 구하고, 이를 부분 해 집합에 추가함
2. 정당성 검사(Feasibility Check) : 새로운 부분 해 집합이 문제의 조건을 만족하는지 검사
3. 해 검사(Solution Check) : 새로운 부분 해 집합이 문제가 있는지 검사하고, 해가 완성되지 않았다면 1번부터 다시 시작

→ 모든 문제에 그리디 알고리즘을 적용할 수 없음을 알 수 있다.

 

 

---

 

[ 예제 1 ] 거스름돈

• 음식점의 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재함
• 손님에게 거슬러 줘야 할 돈이 N원 (N은 항상 10의 배수)
• 거슬러줘야 할 동전의 최소 개수는?

그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제임.

동전의 최소 개수를 구해야 하므로 가장 큰 단위부터 돈을 거슬러 주면 된다.

# Python 코드
def solution(n):
    count = 0
    
    coin_types = [500, 100, 50, 10]
    
    for coin in coin_types:
        count += n //coin
        n %= coin
        
    return count

print(solution(1260))

// Kotlin 코드
fun main(args: Array<String>) {
    println(min_coin(1260))
}

fun min_coin(n: Int) : Int{
    var count = 0
    var money = n

    var coin_types: List<Int> = listOf(500, 100, 50, 10)

    for (coin in coin_types) {
        count += money/coin
        money %= coin
    }

    return count
}

• 화폐의 종류만큼 반복을 수행하므로 화폐의 종류가 N개라고 했을 때, 시간 복잡도는 O(N)
• 이 알고리즘의 시간복잡도는 동전 종류의 수에만 영향을 받음
• 그리디 알고리즘이 가능한 이유? 가장 작은 단위의 동전을 조합하여 큰 단위의 동전을 만들 수 있기 때문

 

 

이것이 취업을 위한 코딩 테스트다 with 파이썬