[알고리즘] 그리디 알고리즘의 특징과 그리디 구분법

그리디 알고리즘 특징

• 그리디 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.
• 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제이다.
• 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.
• 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.
• 일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다.

 

그리디가 가능한 경우 판단 - 거스름돈 줄이기 문제

물건 값이 1200원이고, 받은 돈이 2000원이라면 800원을 거슬러줘야 할 것이다.

위 문제의 거스름돈의 개수를 줄이기 위해 아래 두 가지의 화폐 단위가 있다고 해보자.

1. 500원, 100원, 50원, 10원
2. 500원, 400원, 100원, 50원, 10원

1번의 경우에는 그리디가 가능하지만, 2번의 경우는 그리디로 풀 수 없다.

왜 그럴까?

그리디로 풀기 위해서는 하나의 문제를 다른 부분 문제로 풀 수 있어야 한다.

 

1번의 경우

500원은 100원 5개, 50원 10개, 10원 50개로 만들 수 있다.

100원의 경우 50원 2개, 10원 10개로 만들 수 있다.

50원의 경우 10원 5개로 만들 수 있다.

 

2번의 경우

400원, 100원, 50원, 10원의 경우 각각 하위 문제로 만들 수 있지만,

500원의 경우 100원, 50원, 10원으로는 만들 수 있지만 400원을 여러 개 모아도 500원을 만들 수 없다.

따라서 2번의 경우는 그리디로 풀 수 없는 문제가 된다.

 

그리디의 필수 요소

탐욕적 선택 속성

• 탐욕적 선택은 최적해로 갈 수 있음을 보여야 한다

최적 부분 구조

• 최적화 문제를 정형화하라
  • 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는 것이 보장되어야 한다.

따라서, 원 문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해 임을 증명해야 한다.

 

마치며

동전 거스름 문제나 프림, 크루스칼, 다익스트라와 같이 잘 알려진 그리디 문제가 아니라면 알고리즘 문제에서 그리디를 판단하는 것은 쉽지 않은 것 같다.

그리디라는 것을 알기만 한다면 쉽게 코드를 짤 수 있는 만큼 여러가지 그리디 문제의 유형을 파악하고 있을 필요가 있어 보인다.