Greedy algorithm

알고리즘

Greedy algorithm

DearGreen 2023. 1. 31. 01:56

탐욕 알고리즘(Greedy algorithm)이란?

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행한다.
순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

By - 위키백과

간단히 요약하자면,

1. 그리디 알고리즘은 매 순간 선택마다 조건에 따른 최적의 선택을 한다.

2. 선택을 하는 순간에 대해선 최적이지만, 최종결과값이 알고리즘 전체적으로 최적한 선택으로 볼 수 없다.

2번의 이유는 아래 예시로 간단히 알아 볼 수 있다.

위 그림은 대표적인 그리디 알고리즘의 예시이다.

이진 트리에서 노드의 최종 합계를 되도록 크게 만드는 알고리즘을 짠다고 가정하자.

노드 비교 순간만 큰 값을 선택하는 그리디 알고리즘의 방식의 최종값은 (44)

노드 전체값을 고려한 값을 선택하는 최적 선택 방식의 최종값은 (105) 이다.

이렇게 명백히 두 알고리즘에 차이가 있음을 알 수 있다.

그렇다면 사용자는 전체적으로 최적인 결과값을 주는 최적 선택 알고리즘을 사용하지,

왜 그리디 알고리즘을 사용할까?

그리디 알고리즘은 매 순간의 상황만 고려해 지역적으로만 최적화된 선택을 하지만, 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있어 근사 알고리즘으로 활용할 수 있다.
최적해를 구할 수 있는 문제(매트로이드)가 존재하고, 이런 문제는 그리디 알고리즘을 사용해서 해결할 수 있다고 한다.

대표적인 예제로는 아래 문제가 존재한다.