05. Greedy Algorithm(1)

안녕하세요. 오늘은 Greedy Algorithm. 한국어로는 탐욕적 기법이라고 하는 알고리즘을 소개할까 합니다. DP와 함께 굉장히 유명한 알고리즘인데요. 개념 자체는 이해하기 쉽습니다. 하지만 어려운 문제도 많은만큼 마스터는 어려운 파트죠.

 

탐욕적 기법은 말 그대로

 

탐욕적으로 당장 눈에 보이는 것 중에 가장 맛있어 보이는 부분(이익)

 

만 취하겠다는 것입니다. 물론 이런 방법이 통하지 않는 경우도 있습니다. 도시락 데우기, 파일 합치기 등은 탐욕적 기법이 통하는 유명한 문제입니다. 이런 경우는 여러 번의 선택이 모두 잘못되지 않아야 합니다. 즉, 눈 앞에 보이는 것에 대해서 취한 전략이 그 이후에도 계속 성립해야 한다는 것입니다. 

 

많은 문제들이 딱보고 그리디라고 판단하기는 어려운데요. 쉽게 반례가 떠오르지 않는다면 그리디로 시도해보는 것을 추천드립니다. 풀이가 단순해서 시간복잡도도 작은편인데 역으로 문제는 복잡하게 내는 경우가 많습니다.

 

 

대표적으로 동전문제를 소개해볼까 합니다. 많은 알고리즘 수업에서 동전문제를 다루고 저도 수강했던 알고리즘 수업에서 동전문제를 다루었던 기억이 있는데요. 10, 50, 100, 500원 동전이 있고 수량에 제한이 없다고 할 때, 동전 갯수를 최소로 사용하여 일정한 금액을 만드려면 어떻게 할까요? 

 

만약 880원을 맞춰야 한다면 500 + 100 + 100 + 100 + 50 + 10 + 10 + 10 > 8개의 동전이 최소로 필요할 것입니다. 어떻게 선택했을까요? 큰 금액의 동전을 무조건 선택하는 겁니다. 우리가 처음에 500원을 선택하지 않고 다른 동전을 선택하면 어떻게 될까요? 그 작은 동전들을 모아 결국 500원을 만들게 됩니다. 다른 동전들이 500의 약수이기 때문이죠. 작은 동전들로 큰 동전 액수를 무조건 만들게 된다는 것입니다. 이럴 때는 큰 액수의 동전을 선택이 최선이라는 것을 알고 있습니다. 여기서 전제는 배수라는 성질입니다.

 

배수라는 성질이 어긋나게 되면요? 직접 해보시면 됩니다. 간단한 케이스만으로 쉽게 반례를 제공할 수 있는데요. 만약 700, 220, 10으로 바꾸어 볼까요. 동일하게 880원을 만들때 큰 동전만 선택한다면 700 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 > 19개의 동전이 필요합니다. 만약 220원 짜리 동전을 선택한다면요? 220 + 220 + 220 + 220 > 4개만 필요합니다. 즉, 그리디 알고리즘을 사용할 수 없는 것이죠.

 

이렇게 되는 이유는 무엇일까요? 미적분을 배우시거나

2021.10.22 - [Project/소소하게~] - Finding the root of an equation

Finding the root of an equation

글을 읽어보신 분들이라면 아시겠지만 우리가 구하는 해를 찾기 위해서는 어느 조건이 만족해야 한다는 것입니다. 만약 함수의 최댓값을 찾는다고 생각해 볼까요? 

위키의 Greedy 페이지에서 가져온 사진입니다. A지점에서 찾기 시작했다고 하죠. 우리는 양옆 조금만 시야를 확보할 수 있습니다. 산이라고 생각해 볼까요? 오르막길을 선택하는 것이 산꼭대기에 도달하는 방법이라고 생각할 것입니다. 그러면 우리는 m에 도착할 것입니다. 실제로는 그렇지 않지요. 물론 m은 local한 maximum이긴 합니다. 일정 지역에 한해서 m이 산꼭대기이긴 하죠. 하지만 우리가 구하고자 하는 즉, 전체 지역에서의 꼭대기는 아닙니다. 여기서 감이 오시나요?

우리는 전체를 한번에 보기 힘듧니다. 많은 푼제를 푸시다보면 자주 마주칠 문제죠. 우리가 한타임에 전체를 조망할 수 없다는 것이 항상 어려운 점입니다. 그 상황에서 우리가 어딘가 도착한다면 그것이 local에 해당하는 해인지 global에 해당하는 해인지는 판단하기 어렵습니다.

 

또다른 문제는 무엇일까요? 바로 되돌아가진 않는다는 것입니다. 우리가 A지점에서 오른쪽으로 가길 선택했다면 다시 A지점으로 돌아오진 않는다는 것이죠. 쉽게 생각해보면 A 1m 오른쪽에 A'지점이 있고 이동단위가 1m라면 우리는 A지점에서 시작해서 A'으로 갈 것입니다. 그런데 A'에서 A로 갈까요? No. 우리가 취한 전략으로 A > A'으로 갔다면 A' > A로 갈 순 없습니다 설령 A로 간다하더라도 A지점에서의 선택은 A'이 되겠죠.(A > A' > A > A'...) A지점에서의 최적해는 A'이였으니까요. 즉, 다시 이전상태를 톺아봐야 하는 문제는 그리디 알고리즘으로 해결될 가능성이 낮다는 점을 시사합니다.

 

 

마지막으로 그리디 알고리즘을 정리하겠습니다.

"탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

 

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다."

이 앞에서 설명한 내용인데요. 읽기 편하시라고 위키에서 좀 가져왔습니다. 중요한 것은

 

greedy choice property, optimal substructure

 

입니다. 이것은 많은 문제를 풀면서 체득하실 수 밖에 없어요. 또한 그리디 알고리즘의 한계와 한계점이 시사하는 바에 대해서도 이야기하고 있는데요. 부분적인 해를 구할 수는 있다는 점을 소개해드렸었습니다. 그걸 이용한 것이네요. 즉 알고리즘은 계속해서 미해결 문제들을 풀고 있기 때문에 쉽게 풀리지 않거나 제한된 시간안에 풀기 힘든 문제(NP Problem)같은 경우 cost가 낮은 그리디 알고리즘이 대안이 될 수 있다는 것을 의미합니다.

 

 

추가로 문제를 풀다보시면 아시겠지만 정렬이나 구조체 정의 정도는 미리 학습하시는 것을 추천드립니다. STL과 친숙해질 필요도 있겠군요.

 

 

추가로 알고리즘 카테고리에서는 tag를 신경쓰겠다 한적이 있습니다. 아무래도 추가적인 글을 작성하면 여러분이 보시기에 정렬되어 있지 않아 보기 불편하실거기 때문인데요. 검색을 용이하게 하기 위해 알고리즘 카테고리 안의 Greedy Algorithm과 관련된 모든 글은 Greedy tag를 사용하였습니다. 도움되시길 바라겠습니다.

https://ku320121.tistory.com/tag/Greedy

SONGANG

 

 

 

Reference

https://en.wikipedia.org/wiki/Greedy_algorithm

Greedy algorithm - Wikipedia