[알고리즘] 그리디 알고리즘 (Kotlin)

그리디 알고리즘

그리디(Greedy) 알고리즘, 탐욕 알고리즘이라고도 합니다. 그리디 알고리즘은 여러 가지 경우 중 현재 상황에서 최적의 경우를 선택해 최종적인 결과를 도출해 내는 알고리즘입니다.

이때, 최적의 경우는 문제에 제시된 '최대/최소, 오름차순/내림차순' 같은 조건을 따르면 됩니다.

 

매 순간 '최적'의 경우를 선택하는 알고리즘이기 때문에 어느 순간 최적의 선택일지라도 전체의 경우에서 최적의 선택이 아닐 수도 있습니다. 

따라서 현재의 선택이 전역적으로도 최적의 선택인지를 확인하는 과정이 필요합니다.

 

대표적인 예시로 거스름돈과 관련된 [백준 11047번 : 동전0] 문제를 해결해 보겠습니다.

---

11047번: 동전 0

나의 풀이

fun main() {
    val (n,k) = readLine()!!.split(" ").map { it.toInt() }
    val coinList = ArrayList<Int>(n)
    var coinCnt = 0

    repeat(n) {
        coinList.add(readLine()!!.toInt())
    }

    var result = k

    // 최소 동전 개수를 구하기 위해 내림차순 정렬
    coinList.sortedDescending().forEach {
        if (it <= result) {
            coinCnt += result/it
            result %= it
        }
    }

    println(coinCnt)
}

☞ k보다는 작되 비싼 동전부터 동전의 개수를 추가한다면 '동전 개수의 최소' 조건을 자동으로 만족하기 때문에 위와 같은 방법으로 해결했습니다.

---

+ 백준 1931번 : 회의실 배정

1931번: 회의실 배정

나의 풀이

fun main() {
    val n = readLine()!!.toInt()
    val arr = ArrayList<Pair<Int, Int>>(n)
    var cnt = 1

    repeat(n) {
        var (a, b) = readLine()!!.split(" ").map { it.toInt() }
        arr.add(Pair(a, b))
    }
    // 종료시간 순으로 먼저 정렬하고, 시작시간 순으로 정렬
    arr.sortWith(compareBy(
        {it.second},
        {it.first})
    )

    var endTime = arr[0].second
    arr.forEachIndexed { index, pair ->
        if (index != 0 && endTime <= pair.first) {
            endTime = pair.second
            cnt++
        }
    }
    
    println(cnt)
}

☞ 마찬가지로 그리디 알고리즘을 이용합니다.

Pair<시작시간, 종료시간>가 들어있는 배열을 종료시간 순으로 먼저 정렬하고, 시작시간 순으로 정렬합니다.

이제 이전 회의가 종료되는 시간과 회의가 시작되는 시간을 비교해 종료시간보다 시작시간이 크다면 이전 회의는 시간표 배정이 가능하다고 판단해 cnt를 1 증가시킵니다.