탐욕 알고리즘(1 - greedy 알고리즘 소개)

 

 

○들어가는 글

우리는 지금까지 트리 알고리즘과 완전 탐색의 대해서 알아보았습니다. 그중에서 완전 탐색을 이용한 knapsack 알고리즘을 구현해 보기도 하였습니다. ( https://kuck-su-labor.tistory.com/52 )

하지만 이러한 완전 탐색은 시간복잡도가 높아서 비효율적이라는 이야기도 했었습니다. 따라서 우리는 Greedy 알고리즘을 같이 사용하여 완전 탐색알고리즘의 성능을 높이는 knapsack 알고리즘을 구현해보려고 합니다.

지금까지 완전 탐색을 진행했었으니, 이제는 Greedy 알고리즘을 확인해 보면 되겠죠. 이번 글에서는 Greedy 알고리즘에 대해서 알아보고, 어떠한 특징이 있는지 간단히 알아보려고 합니다. 그리고 다음에는 간단한 실습으로 이 부분을 마무리 지으려고 합니다.

 

○  Greedy 알고리즘이란 ( 그리디 알고리즘의 개요 )

Greedy 알고리즘은 기본적으로 반복과 선택입니다. 각 부분 부분 마다 greedy 알고리즘은 항상 최적의 선택을 반복합니다. 만약 [4, 2, 5, 3, 1] 이라는 배열이 있고, 최적의 조건이 가장 큰 수를 고르는 것이라면, 가장 큰 수의 순서대로 [5, 4, 3, 2, 1]의 순서대로 선택하는 것, 이러한 로직도 어떻게 보면 greedy 알고리즘이라고 할 수 있겠죠. (사실 이는 정렬에 가깝습니다) 즉 greedy 알고리즘이라는 것은 매 상황에서 최적의 선택을 반복하는 알고리즘이라고 할 수 있을 것입니다.

이때 우리는 greedy 알고리즘을 구성하기 위해서 다음과 같은 사항을 고려해 봐야 합니다. 

1. 최적 해 찾기 - 가장 최적의 선택은 무엇인가?

2. 반복 - 언제까지 반복해야 하는가?

 

 

○ Greedy 알고리즘의 예시

Greedy 알고리즘으로써 가장 유명한 문제는 동전 문제입니다.

각 N개의 1원 10원 50원 100원의 동전이 있을 때 가장 적은 수의 동전으로 값을 지불하는 방법

위에서 알아보았듯이 우리는 2가지를 고려해야 합니다.

 

1. 최적 해 찾기 - 가장 최적의 선택은 무엇인가?            2. 반복 - 언제 반복해야 하는가?

 

만약 172원의 값을 지불해야 한다고 합시다. 이러면 가장 적게 동전을 지급하기 위해서는 어떻게 해야 할까요? 가장 적게 동전을 지급하기 위해서는 단위가 작은 동전을 지급해서는 안 됩니다. 그렇게 되면 1원짜리 동전 172개를 내야 할 테니까요. 반대로 큰 동전부터 내야 할 테지요

 

1. 최적 해 찾기 - 가장 최적의 선택은 무엇인가? -> [최적의 선택 : 지급 할 수 있는 가장 큰 값의 동전]

 

그리고 이러한 선택의 반복은 동전으로 모든 값을 지불할 때까지 진행하면 됩니다. 따라서 알고리즘은 다음과 같을 것입니다.

 

1. 최적 해 찾기  ->    1-1 [지급 할 수 있는 가장 큰 값의 동전을 선택한다.]

                                  ->    1-2 [만약 지불할 동전이 없다면 다음으로 큰 동전을 지불한다]

 

2. 반복 - [모든 값을 지불할 때까지 1번을 반복한다]                             

 

코드로 구현을 한다면 다음과 같을 것입니다.

fun main() {

    	var N : Int = 172  // 입력된 값
    	var conins : MutableList<Int> = mutableListOf(1,100,50,10)  // 일부러 섞어놓았습니다.
        var coninnumber : Int = 0  // 동전의 수
        
    	conins.sortDescending() // !가장 큰 값순으로 정렬해야만 합니다. 이 부분이 greedy의 선택 조건이 되는 것입니다. // conins = [100, 50, 10, 1]
    
      
   		while(N!=0){  // 모든 값을 지불 할 때까지 반복한다!
            for(i in 0 .. conins.size -1){ 
               if(N - conins[i] >= 0 ){   // 만약 지불할 수 있는 값인지 순서대로 확인 -> 가능한 큰 동전이 선택된다. 
                     N -= conins[i]      // 값에서 동전만큼 제거한다. 
                   	 coninnumber += 1   // 동전 수를 더한다.
                     break  
               } 
            }
        }
        
        println(coninnumber)
}

어떤 동전이 사용되었는지 더 자세히 알고 싶다면 다음처럼 구현 할 수도 있겠죠.

이러한 알고리즘을 그리디 알고리즘이라고 할 수 있습니다.

 

 

○ Greedy 알고리즘 심화

그리디 알고리즘은 위 처럼 단순해 보입니다. 실제로 그렇지만 심화적으로 들어가면 다룰 것이 많아집니다. 또 추후에 분할 정복법( Divide & Conquer )을 다룰 때 필요하니 짚고 넘어가 봅시다. 

그리디 알고리즘은 크게 아래의 3가지 유형의 문제들을 해결하는데 사용됩니다. 

• 탐욕 선택 속성(greedy choice property)
• 최적 부분 구조(optimal substructure)
• 근사 알고리즘(approximation algorithm)

이러한 것은 그리디 알고리즘을 알아가는데도 유용합니다. 하나하나 살펴 보도록 합시다. 

 

1. 탐욕 선택 속성(greedy choice property)

우선 먼저 탐욕 선택 속성이라는 것은 간단하게 소개하자면, 위에서 설명 했던 것 처럼 항상 최적의 선택을 반복하는  것이 해가 될 수 있는지에 관한 속성입니다. 

이렇게 보면 어렵게 느껴질 수도 있는데 쉽게 이해해 보자면 탐욕 알고리즘이 제대로 작동하기 위한 전제 조건, 우선 이렇게 이해해 봅시다.

이게 무슨 뜻인지, 한 번 예를 들어 보겠습니다. 위의 동전 문제의 동전 단위를 바꾸어서 다시 해 봅시다. 

다음과 같은 결과를 얻을 수 있습니다. 하지만 이상합니다. 가장 적은 수의 값으로 한다면, 5 * 4 = 20으로 동전 4개만으로도 가능한데 말이죠. 우선 이유를 설명해 드리자면, 이러한 경우 greedy 알고리즘이 성립되기 위해서는 요소의 구성요소가 서로를 만들 수 있는 관계가 성립되어야 합니다. 위의 [100, 50, 10, 1]은 서로서로 구성할 수 있었지만 [1, 5, 8]은 그렇지 않았죠.

 

서로를 구성하는 경우 => [ 100 = (50*2) = (10*10) = (1*100) ]

만족하는 이유야 여러 가지가 될 수 있습니다. 가장 중요한 것은 greedy 알고리즘은 항상 최적의 해를 제공하는 것은 아니라는 것입니다. 때문에 아무 선택을 가지고 그리디 알고리즘으로 해결할 수 는 없지요. 결론은 그리디 알고리즘내에서의 최적의 선택은 , “그 선택을  반복하는 것이 해가 된다.” 라는 것이 참인 전제 이여야 합니다.

우리는 위의 동전 문제를 풀면서 전제조건으로  [ 가장 최적의 선택 == 지급 할 수 있는 가장 큰 값의 동전 ] 이라고 정의하였습니다. 실제로 이는 증명된 것이고 ( 증명은 생략하겠습니다 ) 탐욕 선택 속성이 성립되었기 때문에 그리디 알고리즘으로써 해를 얻을 수 있었던 것 입니다.

이렇게 “항상 최적의 선택을 반복하는  것이 해가 참이 된다.” 라는 전제 조건을 탐욕 선택 속성 (greedy choice property)이라고 합니다.  때문에 탐욕 선택 속성이 없는 문제는 그리디 알고리즘으로 해결하기 어렵습니다.

 

 

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

아까전의 동전문제는 각 동전 단위를 나누고, 각 단위마다 지불할 수 있는 양을 구하고 모두 합치면서 최종 해를 구했습니다. 이렇게 그리디 알고리즘은 각 단위마다 최적의 선택을 하는 것을 반복하기를 반복하는데, 이렇게 부분 부분의 해를 합한 것을 최적 부분 구조(optimal substructure) 라고 합니다.

동전 문제는 각 동전마다 조건을 반복했다고 볼 수 있습니다. 

최적 부분 구조는 문제의 최적 해결 방법이 부분 문제에 대한 최적의 해결 방법인 구조입니다. 즉 “전체 문제를 나눈 부분 부분이 있고, 각 부분을 모두 해결해서 합치면 전체를 해결한 것과 같다.” 라고 생각하시면 될 것 같습니다.

한번 예를 들어 봅시다. A부 터부터 D까지 간다고 할 때 지도는 다음과 같다고 생각해 봅시다.

시작부터 끝까지 가장 빠르게 가는 시간을 구하세요

 

위 지도를 보면, 출발지 A와 목적지 D가 있다고 가정할 때, 중간에 경유지 B와 C가 있습니다. 이러한 경우 다음과 같은 문제가 주어졌습니다.

 

A부터 D까지 가는 경로 중에 가장 빨리 갈 수 있는 시간을 구하여라

 

위 문제를 보면, 큰 문제를 작은 문제로 나누기 위해서는 A부터 B까지, B 부터 C까지, C부터 D까지로 세 부분으로 나누어 푸는 것이 일반적일 것입니다.

위와 같이 할 경우 각 단계에서 가장 짧은 시간인 ( 1 + 3 + 1 = 5)가 가장 짧은 시간이자 이 문제의 해가 될 것입니다.

이 처럼  “전체 문제를 나눈 부분 부분이 있고, 각 부분을 모두 해결해서 합치면 전체를 해결한 것과 같다.” 이를 성립한다면 최적 부분 구조(optimal substructure) 라고 합니다.

 

 

3. 그리디 알고리즘이 동작되기 위한 조건 

위에서 언급하였듯이 그리디 알고리즘은 항상 최적의 해를 보장하지 않습니다. 조건이 존재하죠. 그리디 알고리즘으로 잘 동작하기 위해서는 지금까지의 2가지 속성, 즉 탐욕 선택 속성과 최적 부분 구조 를 어느정도 만족해야 합니다. 

다시 말하자면 위의 2가지가 만족되지 않는 알고리즘이라면, 알고리즘이 항상 올바른 해를 반환한다고 보기 힘듭니다.

하지만 반대로 2가지가 만족되지 않더라도, 근사 알고리즘은 올바른  해와 관련이 없기 때문에 어느때나 무난하게 활용이 가능합니다.  다음으로 넘어갑시다.

 

 

4. 근사 알고리즘(approximation algorithm)

아까전에서 다루었든이 우리는 그리디 알고리즘이 항상 최적의 값, 즉 항상 정답을 반환하는 것은 아니라는 것을 알아보았습니다.  하지만 그리디 알고리즘은 무조건 해를 보장하지는 않지만 해와 근접한 결과를 반환합니다. 이렇게 근사한 결과 값을 반환한다는 것을 이용한 알고리즘이 근사 알고리즘(approximation algorithm)입니다. 

근사 알고리즘은 비록 문제의 대한 해로는 작용하지는 않지만 어느정도의 적정선을 보장하는 알고리즘입니다. 이를 활용해서 해를 구할 수는 없지만 알고리즘을 빠르게 개선하는 식으로 사용할 수있습니다. 

이에 대한 활용으로는  knapsack 문제에 적용하여 좀 더 알고리즘의 결과를 빠르게 도출 하는 식으로 활용할 수 있습니다. 이에 대해서는 다뤄야 할 내용이 많습니다. 다음 시간에 실제로 우리가  knapsack 문제를 풀어보면서 근사 알고리즘을 어떻게 활용할 수 있는지 알아봅시다.

 

---

 

○ 이번 글을 마치면서

greedy 알고리즘을 보면서 우리는 greedy 알고리즘에 대해서 알아보았고, greedy 알고리즘의 특징과 greedy 알고리즘은 항상 최적의 해를 반환하지 않는다는 것까지 알아보았습니다. 다음에는 greedy 알고리즘을 통해 활용하거나, 새로운 문제를 가져와서 풀어와 보도록 하죠. 감사합니다.

 

 

ps) 참고:

www.youtube.com/watch?v=2nv7pQO4LTU