Kotlin 연습하기(10) - 그리디 알고리즘

1. 그리디 알고리즘의 정의

그리디 알고리즘은 문제를 해결할 때 현재 상황에서 가장 최선의 선택을 하여 최종 해답을 도출하는 방법이다. 이 때, 각 단계마다 선택하는 것이 최적해를 보장하는 경우에만 효과적이다.

 

 

2. 국부 최적 선택(Local Optimal Choice) 이란??

국부 최적선택이란 각 단계에서 당장 가장 이득이 큰 선택을 하는 것을 의미한다. 예를 들어, 쇼핑할 때 할인율이 가장 높은 상품을 먼저 고르는 것과 비슷하다.

 

 

3. 그리디 알고리즘의 장단점

장점 : 

• 구현이 단순하고 빠르며, 계산 비용이 적다.
• 문제의 크기가 커져도 각 단계의 선택만 고려하면 되므로 효율적이다.

단점 : 

• 매 순간 최선의 선택이 전체 최적해를 보장하지 않을 수 있다.
• 문제에 따라 그리디 알고리즘이 최적해를 찾지 못하는 경우가 있다.

 

4. 대표 문제 : 동전 거스름돈 문제

 - 문제 설명 : 정당한 화폐 단위 (예: 500원, 100원, 50원, 10원)가 주어지고, 거슬러 줘야 하는 금액이 주어졌을 때, 가장 적은 수의 동전으로 거스름돈을 지급하는 방법을 구하는 문제다.

 - 힌트 : 그리디로 접근하면 거슬러 줄 금액이 있을 때, 가장 큰 단위의 동전을 최대한 많이 사용한다. 그 후, 남은 금액에 대해 같은 방식으로 반복한다.

 - 조건 : 이 접근법은 화폐 단위가 "정당한 화폐 단위"일 때 최적해를 보장한다.

 

 

Kotlin을 이용한 동전 거스름돈 문제 구현

fun coinChange(amount: Int, coins: Array<Int>): Int {
    var remaining = amount
    var count = 0

    // 동전 배열은 큰 단위부터 정렬되어 있다고 가정합니다.
    for (coin in coins) {
        if (remaining >= coin) {
            val numCoins = remaining / coin  // 해당 동전으로 몇 개를 사용할 수 있는지 계산
            count += numCoins                 // 총 동전 개수에 더합니다.
            remaining %= coin                 // 남은 금액을 계산합니다.
            println("동전 $coin원: 사용 개수 = $numCoins, 남은 금액 = $remaining")
        }
    }
    return count
}

fun main() {
    // 예제: 거스름돈 1260원, 화폐 단위는 500, 100, 50, 10원
    val amount = 1260
    val coins = arrayOf(500, 100, 50, 10)
    println("총 동전 개수: ${coinChange(amount, coins)}")
}

 

• 초기 변수 설정:
  • remaining 변수는 아직 거슬러 줘야 하는 금액을 저장한다.
  • count 변수는 사용한 동전의 총 개수를 저장한다.
• 동전 단위 순회:
  • 배열 coins는 큰 단위부터 정렬되어 있으므로, 500원부터 차례로 처리한다.
  • 만약 remaining 금액이 현재 동전보다 크거나 같다면,
    remaining / coin으로 해당 동전이 몇 개 필요한지 계산한다.
• 동전 개수 갱신 및 남은 금액 계산:
  • 계산한 동전 개수를 count에 더하고,
  • remaining %= coin으로 남은 금액을 갱신한다.
  • 각 단계에서 현재 동전 단위, 사용 개수, 남은 금액을 출력하여 진행 과정을 확인할 수 있다.
• 최종 결과 반환:
  • 모든 동전 단위를 처리한 후, count를 반환한다.

 

실행결과

동전 500원: 사용 개수 = 2, 남은 금액 = 260
동전 100원: 사용 개수 = 2, 남은 금액 = 60
동전 50원: 사용 개수 = 1, 남은 금액 = 10
동전 10원: 사용 개수 = 1, 남은 금액 = 0
총 동전 개수: 6