탐욕 알고리즘(2) - (greedy 알고리즘 활용 - 강의실 배정문제 )

 

 

○들어가는 글

저번 시간에는 greedy 알고리즘에 대해서 알아보았습니다. 마지막 부분에서 우리는 이 greedy 알고리즘이 항상 해를 반환해 주지는 않는다는 점을 알아보았습니다.

이번 시간에는 1개의 예제 문제를 풀어보면서, 간단하게 greedy 알고리즘을 구현할 때 신경써야 할 것들이 무엇인지 알아보려고 합니다.

 

○ 강의실 배정문제

강의실 배정의 문제입니다. N개의 강의가 있고, 각 강의의 시작 시각과 종료 시간이 있을 때, 서로 겹치지 않는 선에서 가능한 많은 강의를 듣는 방법을 구하는 것입니다.

 

시작 시각 S와 종료 시간 F 가 주어진 임의의 강의 N개가 있을 때, 서로 겹치지 않으면서 최대한 많이 수강하는 방법을 구하시오.

 

[ S > F ] 또는 [강의 시작시간 > 강의 종료시간] 이라고 생각하시면 될 것 같습니다.

 

 

○ 최적 조건의 증명 (탐욕 선택 속성의 만족)

저번 시간에 우리가 알 수 있었던 것은 greedy 알고리즘을 만드는 것은, 최적의 선택을 반복해서 선택하는 것이라고 했었습니다.

문제는 어떤 것이 최적의 선택인가 하는 것입니다. 위의 조건만 해도 어떠한 것이 최적의 조건인지는 알 방법이 없습니다. 이러한 최적의 조건 즉 탐욕 선택 속성(greedy choice property) 을 만족하지 않는다면 제대로 된 결과값이 나오지 않을 것 입니다. 이러한 최적의 조건을 결정하는 데에는 다양한 방법이 있을 수 있습니다.

 그리디 알고리즘으로 구했을 때 강의 시간이 크거나 작은 순서대로 선택할 수 있을 수도 있고, 또는 가장 먼저,  늦게 시작하는 순서대로 선택할 수도 있을 것입니다. 과연 어떤 게 정답일까요?

 

하나 선택해 봅시다. 우선 가장 할 만한 조건은 강의 시간이 작은 순서대로 선택하는 것 입니다. 이렇게 되면 되도록 많은 강의를 들을 수 있어 보입니다. 하지만 그렇지 않죠. 아래의 그림을 보면 그렇지 않다는 것을 알 수 있습니다.

실제로 시간이 적은 순을 조건으로 삼는다면 2개의 강의밖에 선택할 수 없다.

 

대부분의 경우는 되겠지만 우선 위와 같은 경우에는 성립되지 않음으로 이는 올바른 조건은 아닙니다. 그렇다면 어떻게 조건을 알 수 있을까요?

사실 무책임한 말이지만 정해진 방법은 없습니다. 다양한 방법으로 증명하는 방법밖에 없습니다. 명제의 대우 모순을 증명하는 귀납법으로 해결하기도 합니다. 우리가 이를 통해서 증명하는 시간을 가져도 되겠지만, 이렇게 증명까지 가게 된다면 이 글을 길어지게 될 것이기 때문에 우리는 이 부분을 생략하고 가정으로 진행하겠습니다.

 

[가정] 가장 빨리 끝나는 시간의 강의를 선택할수록 많은 강의를 선택할 수 있다.

 

우선 이렇게 넘어갑시다.

 

 

○ 자료의 정렬

우리가 이렇게 최적의 선택 조건을 찾았다면 그다음은 간단합니다. 구현에는 다양한 방법이 있지만 우선 저는 가장 먼저 정렬을 하는 방법을 선택하였습니다.

결국 최적의 조건을 선택하고 이를 반복하는 것이라면, 그 조건의 따라 정렬하는 것이 효율적이기 때문입니다. 그렇게 해야 알고리즘 동작 시 반복하면서 최적의 것을 일일히 찾으려는 코드를 줄일 수 있을 것입니다. 이럴 경우, 단지 정렬된 순서대로 순회하여도 그리디라고 할 수 있지요. 즉 알고리즘의  탐욕 선택 속성(greedy choice property)와 최적 부분 구조(optimal substructure)를 만족한다고 할 수 있습니다. 

다만 정렬은 그리디의 필수사항은 아닙니다. 그리디를 사용하면서 정렬을 하는 경우가 많지만, 필수가 아닌 그저 편하게 하기 위한 선택사항입니다.   

 

위의 조건만 해도 우리는 가장 강의 시간이 빨리 끝나는 것을 선택할 것이기 때문에 강의 종료 시간의 따라 정렬하면 되겠죠.  여기서는 Pair를 사용하므로 second( == 강의 종료시간)을 기준으로 정렬합니다.

 

○ 반복 부분

greedy 알고리즘은 가장 최적의 조건을 반복해서 선택하는 것입니다. 아까 전 정렬을 하였으므로, 여기서는 반복문을 사용하는 방법으로 작성해 보겠습니다. 이번 코드의 경우에는 아주 어려울 것은 없겠죠, while 문을 써서 마지막 시간까지 참조를 모두 끝마칠 때까지 무한 반복을 해도 되겠고, 아니면 그냥 순회하는 방법도 있습니다. 

문제는 강의를 선택하는 수강여부에 있어서, 현재 강의 수강이 가능한 강의만을 고려해야 한다는 것입니다. 즉 해당 시간에 강의를 배정하여서, 그 시간에 다른 강의를 배정할 수 없는 경우는 그 강의는 수강할 수 없습니다.  

해당 강의의 수강여부는 변수 k를 이용합니다. 정렬된 순으로 순회를 진행한다고 하였을 때, 마지막으로 수강한 강의의 인덱스를 저장하여, 그 강의의 끝나는 시간과 비교할 강의의 시작시간을 비교합니다. 수강가능한 강의의 시작시간은 마지막으로 들은 강의의 끝나는 시간보다 항상 크거나 같아야만 수강이 가능합니다.

 

○ 마무리

완성된 코드

fun main() {
 
    
	val SF : MutableList<Pair<Int,Int>> = mutableListOf(Pair(0,7),Pair(10,14),Pair(5,9),Pair(4,8),
                                                       Pair(13,15),Pair(4,6),Pair(14,16),Pair(0,5))
    
 
    SF.sortBy{ i -> i.second }  // 정렬을 해 두는 편이 알고리즘을 작성하는데 편하다. 
    
    
   
    var N : Int = 1  // 맨 처음의 것은 우선 선택된 것으로 취급한다. 따라서 우선 1개는 선택된 것으로 처리함

    
		var k : Int = 0  // 최적의 선택을 일정 반복해야 한다. 
 
        	for( i in 1 .. SF.size -1) {
                if(SF[k].second <= SF[i].first){
	                N ++
	                k = i   
                }
            }
            
        println("고를 수 있는 총 갯수 : $N")
}

전체 코드입니다. 실제로 잘 작동은 하지만 반례가 있는 것 같습니다. 개선의 여지는 필요하지만, greedy 알고리즘을 공부하는 데에는 아마 문제가 없을 것입니다. 저도 다음에 반례를 찾아서 코드를 좀 더 개선해 보도록 하겠습니다.

실제 선택된 강의는 다음과 같다.

 

○ 이번 글을 마치면서

이번 시간에는 문제를 풀면서, greedy 알고리즘을 어떻게 구성하는지 알아보았습니다. 위에서 조건을 증명하고, 정렬하고, 반복하는 것 3가지에 대해서 다뤄 보았습니다.

물론 이는 사실 일반적인 방법에 불과합니다. 때로는 정렬을 하지 않는 경우도 있고, 아예 다른 양상으로 흘러가기도 하겠지요, 이번 글에서는 그냥 제가 이렇게 구성하는 게 편했다는 식으로 써보았고, 무언가 무책임하게 썼다는 느낌도 들기는 합니다. 이렇게 편하게 글을 쓰니 쓰는 입장에서도 즐겁습니다.

다음 시간에서는 지금까지 다루었던 트리(완전 순회)와 greedy 알고리즘(근사 알고리즘)을 통해서 기존에 효율적이지 못했던 완전 탐색 알고리즘을 좀 더 효율적으로 개선하는 과정을 다룰 예정입니다. 2개의 알고리즘에 대해서 복습하는 겸, 활용까지 하는 시간을 가져보도록 하죠. 감사합니다.

 

 

ps)

참고 : 

www.youtube.com/watch?v=7noZLdfHIMQ