탐욕 알고리즘과 예제문제 (Swift)

Greedy algorithm

최적의 해에 가까운 값을 구하기 위해 사용

여러 경우 중 하나를 결정해야 할 때 마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식

동적 계획법(DP)과 비교

길을 찾을때

• 동적계획법: 모든 경우의 길을 전부 확인하고 최단 경로를 찾아서 출발
• 탐욕법: 일단 출발하고 갈림길에 따라 최적의 경로로 생각되는 길을 선택

[출처 및 자세한 내용]

동적 계획법(Dynamic Programming)과 탐욕법(Greedy Algorithm)

예제 1. 동전문제

//동전문제
let coinList = [500, 100, 50, 1]

print(minCoinCount(4720,coinList))

func minCoinCount(_ value: Int,_ coinList : [Int]) -> Int {
    var value = value
    var coinList = coinList
    
    var totalCoinCount = 0
    var details : [(Int,Int)] = []
    //decrease order
    coinList.sort(by: >)
    
    //동전 큰걸 최대한 사용한다.
    for coin in coinList {
        //큰것 부터 사용한다.
        let coinCount = value/coin
        totalCoinCount += coinCount
        value -= coinCount * coin
        details.append((coin,coinCount))
    }
    print(details)
    return totalCoinCount
}

output

[(500, 9), (100, 2), (50, 0), (1, 20)]
31

예제 2. 부분 배낭 문제 (Fractional Knapsack Problem)

//(무게,가치)
var dataList :[(Double,Double)] = [(10,10),(15,12),(20,10),(25,8),(30,5)]

func getMaxValue(_ dataList : [(Double,Double)], _ capacity : Double) -> Double {
    var dataList = dataList
    var capacity = capacity
    var totalValue : Double = 0
    var details : [(Double,Double)] = []
    //무게 대비 가치가 높은 순서대로 소팅 -> 무게/가치
    dataList.sort { $0.0/$0.1 < $1.0/$1.1 }
    for data in dataList {
        if capacity - data.0 >= 0 {
            capacity -= data.0
            totalValue += data.1
            details.append(data)
        }else {
            let fraction = capacity / data.0
            totalValue += data.1 * fraction
            details.append((data.0, fraction))
            break
        }
    }
    print(details)
    return totalValue
}

print(getMaxValue(dataList, 30))

output

[(10.0, 10.0), (15.0, 12.0), (20.0, 0.25)]
24.5

주의할점

최적해에 가까운 값을 구하는것이지 항상 최적해를 찾는 건 아님

ex) 트리에서 root 에서 leaf까지 가장 작은 값을 찾아 가는 경로 찾을 때