[kotlin] 코틀린으로 그리디 알고리즘 작성하기

14 Dec 2023

kotlin

그리디 알고리즘은 매 순간마다 가장 최선의 선택을 하는 알고리즘으로, 보통 최적해를 구하는 데 사용됩니다. 이전 결정이 이후 결과에 영향을 주지 않는다는 점에서 탐욕적인 선택이 이뤄집니다. 이번 포스트에서는 코틀린을 사용하여 그리디 알고리즘을 작성하는 방법에 대해 알아보겠습니다.

그리디 알고리즘 예제

다음은 그리디 알고리즘을 사용하여 주어진 동전의 개수를 최소로 사용하여 거슬러 주는 예제 코드입니다.

fun findMinimumCoins(coins: IntArray, amount: Int): Int {
    var remainingAmount = amount
    var coinCount = 0
    var i = coins.size - 1

    while (i >= 0) {
        val currentCoinValue = coins[i]
        val numberOfCoins = remainingAmount / currentCoinValue

        if (numberOfCoins > 0) {
            coinCount += numberOfCoins
            remainingAmount -= numberOfCoins * currentCoinValue
        }

        i--
    }

    return coinCount
}

fun main() {
    val coins = intArrayOf(500, 100, 50, 10)
    val amount = 1260
    val minimumCoins = findMinimumCoins(coins, amount)
    println("Minimum coins required: $minimumCoins")
}

위 코드는 500원, 100원, 50원, 10원의 동전이 각각 무한대로 있다고 가정했을 때, 주어진 금액을 거슬러주기 위해 필요한 최소 동전 개수를 구하는 예제입니다.

이 예제에서 findMinimumCoins 함수는 coins 배열과 amount를 입력받아 최소 필요한 동전 개수를 반환합니다. 이를 위해 주어진 금액에서 큰 동전부터 시작하여 해당 동전으로 최대한 거슬러 줄 수 있는 만큼 거슬러 주고, 남은 금액에서 이어가면서 동전 개수를 누적해가는 방식으로 동작합니다.

이렇게 하여 그리디 알고리즘이 어떻게 작동하는지 살펴보았습니다. 이제 코틀린으로 간단한 그리디 알고리즘을 작성하는 방법에 대해 확실히 알 수 있을 것입니다.

그리디 알고리즘 예제

참고 자료