📂알고리즘

그리디 알고리즘

정의

그리디 알고리즘 이란 어떤 선택을 할 때 그 순간만을 고려해서 가장 좋은 경우를 고르는 방법이다.

설명

그리드 알고리즘은 탐욕^greed이라는 이름대로 길게 보지 않고 그 순간만을 생각한다. 좋게 말하면 항상 최선을 다하는 것이지만, 크게 보았을 때 이는 현명하지 못할 수도 있다. 다음의 예시를 보자:

왼쪽 0에서 시작해 오른쪽 1에 도착하는 경로를 찾는 문제가 있다고 하자. 그냥 찾는 게 아니라 가장 적은 노드를 거쳐간다고 하면 최적해는 0-A-C-E-1(3) 이 될 것이다. 그러나 그리드 알고리즘은 그 순간 순간 가장 멀리 갈 수 있는 길을 고른다. 따라서 이 문제를 그리드 알고리즘으로 푼다면 그 해는 0-B-D-F-G-H-1(5) 이고, 최적해와 비교해 2번의 비용이 더 발생하게 된다. 가장 처음 선택이 0-B이 아니었다면, 하다 못해 D-F가 아니라 D-E만 골랐어도 더 좋은 해를 고를 수 있었을 것이다.

이렇듯 그리디 알고리즘은 대부분의 맥락에서 어떤 ‘좋은 알고리즘’을 칭한다기보다는 ‘어리석은 방법’일 가능성이 높다. 그러나 알고리즘이라는 것이 동원될 정도로 어려운 문제의 경우 위의 예시처럼 한 눈으로 훑어보는 것만으로 풀릴만큼 일이 간단하지 않을 것이다. 그래서 보통은 그리디 알고리즘으로 나이브하게 풀어본 후 개선된 알고리즘을 만들어간다.