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

728x90

그리디(Greedy) 알고리즘은 '당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'이다.

그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. 또한 '특정한 상황'에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있다.

그리디 알고리즘의 대표적인 예는 거스름 돈 문제이다.

853원의 거스름돈을 주어야 할 때 1원짜리 853개를 주는 것보다 500원 1개, 100원 3개, 50원 1개, 1원 3개를 주는 것이 더 효율적이다. 따라서 이런 경우 '무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘을 사용하면 최적의 해를 보장할 수 있다.

그리디 알고리즘은 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우와 같이 극단적인 문제에 접근한다는 점에서 정렬 기법이 사용되는 경우가 많다.

아래의 그림을 보자.

최단 경로를 찾기 위해 그리디 알고리즘을 사용하여 결과를 얻는다면, A-C-G-I-J(19)의 결과가 나올 것이다. 하지만 위 알고리즘에서 최적의 해는 A-B-E-H-J(12)이다.

이처럼 그리디 알고리즘으로 최적의 해를 보장하는 경우도 많으나 그렇지 못한 경우가 더 많다.

그럴 때는 다이나믹 프로그래밍(Dynamic Programming) 등의 기타 알고리즘 기법을 적용해야 하기도 한다.

끝이 없는 배움의 끝