Kotlin을 활용한 그리디 알고리즘의 이해와 적용(동전 교환, 활동 선택)

그리디 알고리즘(Greedy Algorithm)은 매 순간 최적의 선택을 하여 최종적인 해답에 도달하는 방식으로, 각 단계에서의 최선의 해결책이 전체 문제의 최선의 해결책이 되는 경우에 적합합니다. 이러한 접근 방식은 문제를 효율적으로 단순화시킬 수 있으며, 특히 최적화 문제에서 자주 사용됩니다. Kotlin 언어의 간결함과 표현력을 활용하여 그리디 알고리즘을 구현하는 방법을 알아보겠습니다. 여기서는 동전 교환 문제와 활동 선택 문제(Activity Selection Problem)를 예로 들어 설명합니다.

동전 교환 문제

동전 교환 문제에서는 주어진 동전들을 사용하여 특정 금액을 만드는데 필요한 최소 동전의 수를 찾는 것입니다. 그리디 알고리즘을 사용할 때는 가장 큰 단위의 동전부터 사용하는 것이 일반적입니다.

fun coinChangeGreedy(coins: IntArray, amount: Int): Int {
    var remainingAmount = amount
    var coinCount = 0
    coins.sortDescending() // 동전을 내림차순으로 정렬
    
    for (coin in coins) {
        while (remainingAmount >= coin) {
            remainingAmount -= coin
            coinCount++
        }
        if (remainingAmount == 0) break
    }
    
    return if (remainingAmount == 0) coinCount else -1
}

 

이 코드는 가장 큰 동전부터 차례대로 사용하여 금액을 만듭니다. 모든 금액을 만들 수 있다면 사용된 동전의 수를 반환하고, 만들 수 없다면 -1을 반환합니다.

활동 선택 문제

활동 선택 문제는 여러 활동이 주어졌을 때, 각 활동이 시작 시간과 종료 시간을 가지고 있으며, 한 번에 하나의 활동만 선택할 수 있는 조건에서 최대 몇 개의 활동을 선택할 수 있는지를 결정하는 문제입니다. 그리디 알고리즘을 적용할 때는 종료 시간이 빠른 활동부터 선택하는 것이 일반적입니다.

fun activitySelection(startTimes: IntArray, endTimes: IntArray): Int {
    val activities = startTimes.indices.map { index -> Pair(startTimes[index], endTimes[index]) }
    .sortedBy { it.second } // 종료 시간을 기준으로 활동을 정렬
    
    var count = 1 // 첫 번째 활동은 항상 선택
    var endTime = activities[0].second
    
    for (i in 1 until activities.size) {
        if (activities[i].first >= endTime) {
            // 이전 활동이 끝난 후에 시작하는 활동을 선택
            endTime = activities[i].second
            count++
        }
    }
    
    return count
}

 

이 코드는 각 활동을 종료 시간 기준으로 정렬한 후, 가능한 많은 활동을 선택합니다. 첫 번째 활동을 선택한 뒤, 선택된 활동의 종료 시간 이후에 시작하는 활동 중 가장 빨리 끝나는 활동을 차례대로 선택합니다.

 

그리디 알고리즘은 문제를 해결하기 위한 간단하면서도 효율적인 접근법을 제공합니다. Kotlin의 간결한 문법과 표현력을 활용하면, 복잡한 최적화 문제를 해결하는 강력한 그리디 알고리즘을 쉽고 빠르게 구현할 수 있습니다. 그러나 그리디 알고리즘을 적용하기 전에는 해당 문제가 그리디 알고리즘의 조건을 만족하는지 검토하는 것이 중요합니다.