알고리즘 : 탐욕법 (Greedy)

탐욕법은 문제의 특징을 이용해, 탐색 횟수 자체를 줄여 속도를 향상시키는 일종의 테크닉이다.

 

탐욕법(이하 그리디)은 휴리스틱 알고리즘으로서, 그 순간의 최적을 취해 나가는 형태로 구성된다. 휴리스틱에 대해 아직 공부하지 않은 채로 위 문장을 보면 이해가 가지 않을 것이다. 하지만 DP와 마찬가지로 그리디 또한 우리가 본능적으로 사용할 수 있는 개념이다.

---

우리가 본능적으로 시행하고 있는 그리디 문제를 하나 제시해 보겠다.

바구니에 구슬이 15개 있는데, 이 구슬에는 1부터 15까지의 숫자가 적혀있다. 당신은 바구니에서 구슬을 하나씩 뽑아 가져 갈 수 있는데, 구슬들에 적힌 숫자의 합이 30 이 되어야 되도록 구슬을 가져갈 수 있다. 예를 들어 9, 10, 11 구슬을 뽑으면 셋 다 가져갈 수 있지만 13, 14, 15 구슬을 뽑으면 구슬을 가져갈 수 없다. 15 구슬 이후에 3 구슬을 뽑는다고 하더라도 13, 14, 3을 가져갈 수는 없다. (= 연속적으로 가져가야 한다.)

당신은 최대한 많은 구슬을 꺼내가고 싶다. 하지만 랜덤 하게 정렬되어 있기 때문에 원하는 숫자를 뽑을 수는 없는 상황이다.

 

이 문제를 가지고 그리디를 설명하고자 한다.

위 문제를 간단하게 시뮬레이션 해보았다. 당연히 우리는 구슬의 합이 30을 초과하는 순간에 더 이상 구슬을 뽑는 시도를 하지 않을 것이다. 왜냐하면 여기서 아무리 작은 구슬을 더 뽑아봐야 가져갈 수 없기 때문이다.

 

그리디에서는 구슬의 합이 30 이상이 된 이후에도 구슬을 뽑는 시도를 하는 상태, 즉  어떤 경우에도 올바른 답을 구할 수 없는 상태를 "유망하지 않다." 고 표현한다.

그리디의 아이디어는 여기서 나온다. "유망하지 않은 경로에 대한 연산을 하지 않는 방법으로 전체 연산 횟수 자체를 줄여버리자!"

 

 

그리디를 사용함에 있어 주의할 점은 "유망하지 않다."의 기준을 어떻게 잡느냐에 대한 부분과, 그 순간의 "가장 유망한" 답이 정말로 최종적인 답이 될 수 있느냐 에 대한 부분을 주의해야 한다. 두 가지 유의점에 대해 살펴보자.

---

먼저 유망의 기준을 잘못 설정하거나, 문제 특성상 기준을 설정하기 매우 힘든 경우 그리디로 정답을 구하기는 힘들다.

 

예를 들어 위와 같은 문제에서, 구슬에 적힌 숫자 범위를 -15 ~ +15 범위로 변경한다면 더 이상 30을 초과한 상태가 "유망하지 않은" 상태가 아니다.

 

 

우리는 구슬을 최대한 많이 가져가고자 했다. 첫 예시와 같이 30을 넘기면 멈추는 그리디적 접근을 시도했다면 7개나 가져갈 수 있던 구슬을 4개만 챙기게 되어 오답이다.

 

이 경우 유망하지 않다의 기준을 어떻게 설정해야 할까? 단순히 일정 값을 넘기면 유망하지 않다는 기준으로는 정답을 도출할 수 없다. (예를 들어 유망 기준을 45로 세웠다고 한다면 15, 14, 13, 12, -13, -11이라는 반례가 존재한다.)

---

그 순간의 "가장 유망한" 답이 정말로 최종적인 답이 될 수 있느냐 (= 국부적 최적해가 전체의 최적해의 부분집합인가) 또한 고민해 볼 수 있는 내용이다.

 

위와 같은 문제에서, 구슬의 숫자 범위의 제한을 풀고 연속적으로 취해야 한다는 부분도 제외해보자.

예를 들어 1, 100, 20, 9 순으로 구슬을 뽑았을 때, 가운데 있는 100 구슬은 취하지 않고 1, 20, 9의 3개를 가져갈 수 있다.

 

아래의 구슬 배열을 대상으로 새로운 규칙을 이용해 문제를 풀다보면 100 구슬에서 고민이 생긴다.

 

 

처음 두 번째 구슬을 뽑은 시점에서는 30을 훨씬 넘기기 때문에 챙기지 않는 것이 더 나아 보일 수 있다. 즉 두 번째 구슬을 뽑는 시점까지만 해도, 100 구슬은 취하지 않는 것이 더 최적이다. 하지만 그렇게 되면 남은 구슬을 다 뽑더라도, 어떻게 해서도 30을 만들 수 없다. 

 

지금은 배열의 길이가 짧아서 금세 계산이 가능했지만 문제가 복잡해질수록 그 순간의 "가장 유망한" 답이 정말로 최종적인 답이 될 수 있느냐는 어려운 문제가 된다.

---

지금까지 포스팅해온 알고리즘은 기본적으로 느리더라도 항상 정답이 나올 수 있는 알고리즘이었다, 하지만 그리디는 그와 반대이다. 빠르지만 정답이 나오지 않을 수 있는 알고리즘이다.

 

그렇기 때문에 문제 해석력과 판단력이 중요하다. 꼭 문제 전체에 대해 그리디를 써야만 하는 것은 아니다. 문제의 일부나, 혹은 문제를 풀기 위한 사전 작업 (예를 들어 preprocessing)등 에서 부분적으로 사용하는 것도 가능하다. 잘 사용하면 매우 강력한 알고리즘 이기 때문에 많은 연습을 하는 것을 추천한다.

 

 

 

대표적인 기본 그리디 문제로는 N-Queens가 있으며 이전 포스팅한 동전 2 문제에서도 목표한 금액 이후로는 애초 처리를 하지 않은 부분이 그리디를 응용한 부분이라고 할 수 있다.

 

BOJ 2294번 동전 2