[C++ 알고리즘] 그리디(탐욕법,Greedy Algorithm)

개념

그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 실제 그리디 알고리즘을 검색하면 아래와 같이 나온다.

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

일반적으로 생각했을 때 눈앞의 이익만을 쫓는 것이 최적의 선택이라고는 할 수 없다. 가령 아래와 같은 상황이 있다고 생각해보자. 

---

예제 1

각 그림의 적힌 숫자는 문제를 푸는데 걸리는 시간이고 우리는 가장 빠른 시간안에 level1, level2, level3문제를 하나씩 해결하려 한다. 이때 문제를 푸는 시간을 최소화 하려면 어떻게 해야 할까?

 

앞서 설명했듯이 그리디는 뒷 상황은 생각하지 않는다. 단순히 눈 앞의 이익만을 추구하는 알고리즘이다. 그래서 그리디 알고리즘을 적용한다면 아래와 같이 될 것이다. 총 45분이 소요된다.

그렇지만 실제로 문제를 푸는 시간을 최소화 하는 방법은 아래와 같다. 42분이 소요된다.

여기까지 봤을 때에는 그리디 알고리즘을 도대체 어디다 쓰나 싶을 수도 있다. 그러나 이 알고리즘은 단순한만큼 실행 시간이 빠르다. 그리디 문제를 설명하는 가장 대표적인 예시는 동전문제이다. 아래 문제를 풀어보도록 하자.

---

예제 2

500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해서 1410원을 만든다고 하자. 이때 사용하는 동전의 개수는 몇개인가? 

 

이 문제를 접했다면 일반적으로 500원을 사용할 수 있는 한도까지 사용할 것이다. 그래서 500원짜리 2개로 1000원을 만들고, 100원짜리 4개로 400원을, 10원 동전 1개로 10원을 만들어 1410원을 완성할 것이다. 그래서 이 문제의 답은 7개이다. 이 문제에는 그리디 알고리즘이 사용되었다. 쓸 수 있는 동전 중 가장 액수가 큰 것부터 순서대로 사용해 나간 것이다. 이 행동을 반복하면 문제를 풀어낼 수 있다.

 

이 문제를 위와 같이 단순한 방법으로 풀어낼 수 있는 이유는 작은 액수 동전이 큰 액수 동전의 약수이기 때문이다. 즉, 100원 5개로 만들수 있는 액수는 500원 동전 한개로 만들 수 있다. 그렇기 때문에 큰 액수의 동전부터 사용해 나가면 가장 적은 동전을 사용한다고 보장할 수 있는 것이다.

---

정리를 해보자면 그리디 알고리즘은 특정 상황에서만 사용할 수 있다. 즉 그리디를 사용한 방법이 정답이라는 보장이 되어야 사용할 수 있다. 위에서 봤듯이 예제 2의 경우 동전간에 배수, 약수 관계가 성립했기 때문에 그리디를 사용할 수 있었다. 만일 500원 400원 100원 동전으로 2800원을 만든다고 가정해보자. 위에서 한 방식대로 500원 동전부터 사용을 한다면 500원 5개, 100원 3개를 이용해 총 8개의 동전을 사용한다. 하지만 가장 동전을 적게 사용하는 방법은 500원 동전을 4개, 400원 동전을 2개, 총 6개의 동전을 사용하는 방법이다. 그래서 앞에서 말했듯 그리디를 사용하려면 이 방법이 최선이다 라는 근거가 있어야 한다.

 

그래서 모두 그런것은 아니지만 그리디 문제는 일반적으로 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다. 그리고 그리디를 사용할 수 있는 조건이 주어진다. 위 동전문제는 단순한 예시지만 동전간의 배수, 약수 관계가 그 조건이다. 물론 이러한 조건은 문제 내에 숨겨져있어 찾아내야 하는 경우가 많다.

그리디 알고리즘


1. 일반적으로 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 최대/최소의 경우의 수를 구할것을 요구하는 문제들이다.

2. 그리디를 사용할 수 있는 조건이 주어진다. (주로 문제를 읽고 조건을 찾아야한다.)

3.정렬을 한 뒤 그것을 이용해 푸는 문제가 많다. (위 동전문제의 경우에도 동전을 내림차순으로 정렬한 뒤 하나 하나 사용해 나가야 할 것이다.)

마지막으로 아래 문제를 보도록 하자.

 

이 문제는 나동빈님의 강의 영상에서 나오는 문제이다.

https://www.youtube.com/watch?v=2zjoKjt97vQ&t=1913s 

이 문제 역시 그리디로 풀어낼 수 있는데 그 이유는 N에서 1을 빼는 것 보다 K로 나누는 것이 더 빨리 1을 만들 수 있다는 것이 보장되기 때문이다. 즉 K로 나눠질 때마다 나누고, 그것이 되지 않으면 1을 빼는것을 반복하면 되는 것이다.

 

같이 풀면 좋은 문제

문제를 많이 풀어보면서 "이런것이 그리디구나" 하는 감을 익혀가는 것이 좋을 것 같다.

 

 

아래 두 문제는 그리디라는 것만 알면  어렵지 않게 풀어낼 수 있다.

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

4796번: 캠핑

 

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

2839번: 설탕 배달

---

그리디 문제 특성상 어떻게 해야 최적해를 구할 수 있을까?를 많이 고민해 보며 풀어야 한다. 아래 문제 역시 마찬가지이다. 1 1과 같이 시작하는 시간과 끝나는 시간이 같을 경우도 있다는 것을 고려하며 문제를 풀어보자. 또 어떤 기준으로 정렬하는것이 좋을지 고민해보자.

 

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

1931번: 회의실 배정