[알고리즘] 패스트캠퍼스 챌린지 27일차

탐욕 알고리즘(Greedy Algorithm)

• Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움
• 최적의 해에 가까운 값을 구하기 위해 사용됨
• 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

오호오

문제들로 이해하기

 

 

문제1: 동전 문제¶

• 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
  • 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
  • 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

 

=> 동전의 갯수가 가장 적으려면? 당연히 4720원을 가장 큰 값인 500원으로 먼저 최대한 많이 채우고, 그다음으로 큰 100원으로 최대한 채우고.. 그렇게 1원까지 채우면 된다.

 

let coinList: [Int] = [500, 100, 50, 1]
func coinCount(value: Int, coinList: [Int]) -> Int {
    var totalCount: Int = 0
    // coin list that we choose every time
    var details: [[Int]] = []
    
    // sort coin list from high to low
    var sortedCoinList: [Int] = coinList
    sortedCoinList.sort { $0 > $1 } // [500, 100, 50, 1]
    
    var pay: Int = value
    for coin in sortedCoinList {
        let count: Int = pay / coin
        totalCount += count
        pay -= count * coin
        details.append([coin, count])
    }
    
    print(details)
    return totalCount
}

print(coinCount(value: 4720, coinList: [500, 50, 100, 1]))

오!!!

어떤 코인이 몇개 사용되었는지도 details 배열로 체크해봤다.

예상한대로 잘 나온당 :)

코인 리스트(coin list)를 큰 값 순서대로 소팅한 이유는 값이 큰 동전부터 채워나가기 위함이다.

 

 

 

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

• 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
  • 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
  • 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름
    • Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem 으로 부름)

=> 최대 가치를 가지도록 물건을 넣으려면 당연히 무게 대비 가치가 높은 친구먼저 채우면 된다.

let dataList: [(w: Float, v: Float)] = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]
func fractionalKnapsack(limit: Float, data: [(w: Float, v: Float)]) -> Float {
    var totalValue: Float = 0
    var details: [(w: Float, v: Float, p: Float)] = []
    // sort from high value / weight
    var dataList = data
    dataList.sort {$0.v / $0.w > $1.v / $1.w}
    
    var capacity: Float = limit
    for data in dataList {
        if capacity - data.w >= 0 {
            capacity -= data.w
            totalValue += data.v
            details.append((data.w, data.v, 1))
        } else {
            // fraction
            let fraction = capacity / data.w
            totalValue += data.v * fraction
            details.append((data.w, data.v, fraction))
            break
        }
    }
    print(details)
    return totalValue
}

 

쪼개서 넣을 수 있다는거 까먹고 처음에 Int 형으로 했다가 나중에 Float 형으로 다 바꿔줬다^^;;

최대 기준치를 채우기 위해 기준 무게 당 가치로 계산한다는 것과, 쪼개서도 채울 수 있다는 점에서 위에 동전 문제와 차이가 있지만,

전체적으로 푸는 방식은 동일했다.

 

 

탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용
• 반드시 최적의 해를 구할 수 있는 것은 아니기 때문
• 최적의 해에 가까운 값을 구하는 방법 중의 하나임

 

탐욕 알고리즘 한계

위의 경우에서 최적의 경로를 찾아보면

시작 -> 10 -> 5 => 15

이 경우가 가장 최적이다.

근데 탐욕 알고리즘을 통해 최적의 경우를 찾으면, 매 순간 선택 시 최적의 경우를 선택하기 때문에,

시작 -> 7 -> 12 => 19

이므로 최적의 경로를 선택하지 않는다.

이런 점에서 한계가 있음!!

 

오늘 인증샷. Swift Playground ㅎㅎ

 

오늘 강의 들으면서 신입때 봤던 코딩테스트들 많이 스쳐지나갔다.. 또륵

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.