[알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘이란?

Greedy를 해석해보면 "탐욕스러운"이다.

이 때문에 그리디 알고리즘을 다른 말로 탐욕 알고리즘이라고도 한다.

이 알고리즘은 선택을 할 때마다 최적의 상황만을 선택해 최종적으로 최적의 결과에 도달하게 된다.

 

여러 선택이 있을 때, 모든 경우의 수에서 최적의 선택을 했다고 하자.

이때 최적의 선택만을 골랐다 해서 최적의 결과만 나오는 것은 아니다.

최적의 선택이 모여 조금 덜 한 결과가 나오는 경우의 수가 있을 수도 있다.

 

그리디 알고리즘은 위와 같은 경우가 있어서는 안되며, 항상 최적의 선택만을 하여 최적의 결과가 나와야 하는 알고리즘이다.

정당성 증명

1. 탐욕적 선택 속성(Greedy Choice Property): 현재의 선택이 이후의 선택에 영향을 주지 않으면서, 최적의 선택인 것을 의미한다. 즉, 현재 선택으로 최적의 결론에 도달해야한다는 것이다.
2. 최적 부분 구조 조건(Optimal Substructure): 전체적인 문제에 대한 최적 해결 방법은 부분 문제에 대해서도 최적의 해결 방법이어야 한다. 즉, 전체적인 문제 내부의 부분 문제에서도 최적해가 도출되어야 한다는 의미이다.

그리디(Greedy) 알고리즘의 예시

1. 거스름돈의 갯수 줄이기

그리디 알고리즘의 가장 기본적이면서 널리 알려져있는 문제이다.

온라인 저지 사이트인 백준에도 있는 문제로 그리디 알고리즘에 입문하기 좋은 문제이다.

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

5585번: 거스름돈

문제의 예제로 예시를 들어보고자 한다.

500원, 100원, 50원, 10원, 5원, 1원짜리 동전이 있다.

380원짜리 물건을 살 때, 1000원을 냈다고 한다.

즉, 620원의 거스름돈을 받아야 하는데, 동전의 갯수를 가장 적게 해야 한다.

 

우리는 쉽게 가장 큰 액수의 동전부터 거슬러 받으면 된다는 것을 떠올릴 수 있다.

이에 대한 정당성 검사를 해보자.

• 큰 단위는 항상 작은 단위의 배수이다.( 500 -> 100 * 5, 50 * 10, 10 * 50, ...)
  → 즉, 단위가 큰 것을 선택해야 가장 적은 갯수의 동전을 받을 수 있다.
• 받아야하는 거스름돈보다 많은 거스름돈을 받을 수 없다
  -> 즉, 현재 받아야하는 거스름돈보단 작은 단위의 동전이어야 한다.

이를 통해 우리는 620원의 거스름돈을 받아야할 때, 500원 동전 1개, 100원 동전 1개, 10원 동전 2개를 받아야 한다는 결론을 도출할 수 있게 된다.