탐욕법(Greedy)

 

탐욕 알고리즘(Greedy algorithm)

 

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 최종적(전역적)으로 최적인 문제들이다.

 

탐욕법으로 문제를 해결하기 위한조건

 

1. 탐욕스런 선택 성질(greedy choice property)

 - 앞선 선택이 이후의 선택에 영향을 주지 않는다.

 - 각 지역적 최적의 선택이 모두 전체에 포함됨

 

2. 최적 부분 구조 조건(optimal substructure)

- 전체 문제를 작은 부분으로 나누어 해결 할 때,  전체 문제의 해결방법이 부분문제의 최적의 해결방법들로 구성된다. 

 

실제 문제 풀이에서 필요한것. 

기본적이고 합리적인 아이디어 와 예시를 통해 과연 최적해가 맞는가? 인지를 분석한다. 

*  많은 경우 입력값이 크다. 그렇기 때문에 완전탐색이 불가능하다. 

 

- 현재 최적의 선택이 다음 선택에 영향을 주는가?

- 무엇을 욕심낼것인가?

-->  정렬 및  우선순위큐의 기준이된다.

 

 

동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

이문제의 핵심은

 

"Ai는 Ai-1의 배수" --> 즉, 모든 동전은 전부 (작은동전 * X) => 큰 동전을 만들수 있기 때문에 

동전을 정렬시켜 최대한 큰동전을 가지고 금액을 만들려고 노력하면 된다.

 

*참고 모든 동전들이 배수가 아니라면 최적해가 성립하지 않는다

예시) 금액 800 동전 500 400 100 이라면

500원 1개 100원 3개 

400원 2개

 

code

var n = 0
var k = 0

lateinit var arr: IntArray
fun main() = with(System.`in`.bufferedReader()) {

    val info = readLine().split(" ").map { it.toInt() }
    n = info[0]
    k = info[1]

    arr = IntArray(n) {
        readLine().toInt()
    }
    arr.sortDescending()

    var cnt = 0
    for (coin in arr) {
        while (k >= coin){
            k -= coin
            cnt += 1
        }
    }
    println(cnt)
}

 

 

강의실 배정.

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

 N (1 ≤ N ≤ 200_000)
 Si,Ti (0 ≤ Si < Ti ≤ 10^9)

수업이 끝난 직후에 다음 수업을 시작

강의를 안할수는 없음 -> "시작시간으로 정렬" 하고 시작 시간이 같다면 끝나는 시간으로 정렬.

수업이 끝나는 시간이 중요하며 수업이 "빨리 끝나서" 강의실을 쓸 수 있으면 재활용 --> 우선순위 큐의 기준. 

 

일단 강의실을 배정한다.(pq에 일단 넣음.)

강의가 끝나 재활용 있다면 pq에서 내보낸다. 

출력 pq.size

import java.util.PriorityQueue

var n = 0

lateinit var lectureArr: Array<Pair<Int, Int>>
val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
fun main() = with(System.`in`.bufferedReader()) {

    n = readLine().toInt()

    lectureArr = Array(n) { 0 to 0 }
    for (i in 0 until n) {
        val info = readLine().split(" ").map { it.toInt() }
        lectureArr[i] = info[0] to info[1]
    }
    lectureArr.sortWith(compareBy<Pair<Int, Int>> { it.first }.thenBy { it.second })

    for (i in 0 until lectureArr.size) {
        pq.add(lectureArr[i])
        if (pq.peek().second <= lectureArr[i].first) {
            pq.poll()
        }
    }
    println(pq.size)
}

 

회의실 배정.

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

"한 개의 회의실"이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

각 회의는 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수

 

회의실이 1개이기 때문에 회의가 끝나는 시간이 가장 중요하다.

즉, 모든 회의를 "끝나는 시간이 빠른것"으로 정렬해서 끝나는 시간이 같다면 시작하는 시간으로 정렬한다. 

그후 그냥 시작 및 끝나는 시간을 업데이트 하면서 회의 갯수를 세어준다.

var n = 0
var answer = 1

fun main() = with(System.`in`.bufferedReader()) {

    n = readLine().toInt()

    val arr = Array(n) {
        val info = readLine().split(" ").map { it.toInt() }
        info[0] to info[1]
    }

    val times = arr.sortedWith(compareBy<Pair<Int, Int>> { it.second }.thenBy { it.first })
//    println(times.joinToString(" "))
    var start = times[0].first
    var end = times[0].second

    for (i in 1 until n){
        if (times[i].first < end) continue
        start = times[i].first
        end = times[i].second
        answer += 1
    }
    println(answer)
}