[Kotlin] 그리디 알고리즘(탐욕 알고리즘)
[fastcampus 알고리즘 강의 내용 참고]
탐욕 알고리즘이란 최적의 해에 가까운 값을 구하기 위해 사용됩니다.
즉, 여러 가지 경우 중에서 하나를 결정할 때, 매 순간마다 최적의 경우만 선택하는 방식을
채택해서 최종적인 값을 구합니다.
예를 들어보겠습니다.
문제1) 동전 문제
1원, 50원, 100원, 500원 동전이 주어질 때, 가장 적게 지불하는 동전의 수를 구하기
//val coinList = listOf(1,100,50,500)
private fun Int.coinProblem(list: List<Int>) : Int {
//외부로부터 숫자를 전달받을 때 항상 고정값이므로 Int.함수명을 이용
//항상 최적을 따라야 하기 때문에 가장 큰 숫자부터 내림차순으로 정렬
val coinList = list.sortedDescending()
var coinCount = 0 // 전체 코인 수
var money = this // this는 Int.coinProblem을 뜻함
var coinNum: Int // 각각의 코인마다 소모된 수
for(coin in coinList) {
coinNum = money / coin
coinCount += coinNum
money -= coinNum * coin // 코인의 양 * 코인
}
return coinCount
}
fun main() {
val coinList = listOf(1,100,50,500)
println(4720.coinProblem(coinList))
}
500원은 9개, 100원은 2개, 50원은 0개, 1원은 20개로 총 31개가 사용됨을 확인할 수 있습니다.
그리디 알고리즘 == 매 순간마다 최적의 경우를 탐색한다.
머릿 속에 떠올리셨나요?
다음 문제로 넘어가겠습니다.
문제2) 부분 배낭 문제
무게 제한이 K인 배낭에 최대 가치를 가지도록 물건을 넣는 문제 (무게 : w, 가치 : v)
위의 문제의 핵심은 물건을 "쪼갤 수 있다" 입니다. 그래서 Fractional Knapsack Problem이라고도 불리우며,
이와 반대되어 물건을 쪼개서 넣을 수 없는 배낭 문제는 0/1 Knapsack Problem 라고 합니다. 이는 그리디 알고리즘으로 해결할 수 없고, 동적 프로그래밍(DP)로 해결할 수 있습니다.
다시 문제로 돌아와서, 각각의 물건의 무게, 가치를 설정하겠습니다.
| 물건 (i) | 물건1 | 물건2 | 물건3 | 물건4 | 물건5 |
| 무게 (w) | 20 | 15 | 10 | 25 | 30 |
| 가치 (v) | 10 | 12 | 10 | 8 | 5 |
먼저 그리디 알고리즘은 매 순간 최적의 경우를 선택한다고 했습니다.
그렇다면 무게가 가장 작은 값으로부터 가방을 채워나가야 합니다.
코드로 설명하겠습니다.
//val backpack = hashMapOf(
// 20 to 1, 15 to 12, 10 to 10, 25 to 8, 30 to 5)
//반환형이 Double인 이유는 물건을 쪼갤 때 소수점이 포함될 수 있기 때문
private fun fractionalKnapsack(backpack : HashMap<Int,Int>, value : Int): Double {
// .toSortedMap()으로 key에 대해 오름차순으로 정렬
val sortedBackpack = backpack.toSortedMap()
var totalValue = 0.0
var capacity = value
val list = mutableListOf<Any>() // (test)각각의 물건마다 얼만큼 저장됐는지 확인하는 리스트
for(i in sortedBackpack) {
if(capacity - i.key >= 0) {
capacity -= i.key
totalValue += i.value
list.add(1) //모든 물건이 들어갔음을 표시하기 위해 1 저장
} else {
// double으로 소수점 이하를 출력하기 위해서는
// 변수에 double형, 우측에서는 최소 한 개 이상 toDouble()으로 형 변환시켜야 함
val fraction = capacity / i.key.toDouble()
// 전체 값에다가 해당 가치를 넣을 수 있는만큼 쪼개는 작업
totalValue += i.value * fraction
list.add(fraction)
break
}
}
//test
list.forEach {
print("$it ")
}
println()
return totalValue
}
fun main() {
val backpack = hashMapOf(
15 to 12, 10 to 10, 20 to 10, 25 to 8, 30 to 5)
println(fractionalKnapsack(backpack, 30))
}
값이 정상적으로 출력됨을 확인할 수 있습니다.
이상 마무리하며 다시 머릿 속에서 떠올려 봅니다...
그리디 알고리즘 == 매 순간마다 최적의 경우를 탐색한다.
번외) 그리디 알고리즘의 한계
만약 가장 큰 값을 찾도록 시작 노드로부터 탐색한다고 가정할 때
그리디 알고리즘을 이용하면
7과 10이 있을 때 -> 10 선택
5와 7이 있을 때 -> 7 선택
하지만 최댓값은 15이기 때문에 모순임을 알 수 있다.