📌 알고리즘 - 그리디 알고리즘 개념

Greedy Algorithm 이란?

완전 탐색, 동적 계획법처럼 답을 구하는 과정을 여러 개의 단계로 나누어 답을 만들어가는 과정은 비슷하지만, 각 단계에서 가능한 모든 답을 계산하여 전체적으로 가장 좋은 답을 선택하는 것이 아니라 각 단계에서 가장 좋은 답을 선택하는 점이 완전 탐색, 동적 계획법과 다른점이다.

그리디 알고리즘은 "답을 도출하는 과정 중 매 순간 최고의 선택을 해서 결과적으로 최적의 해를 도출하자"로 표현 할 수 있다.

그런데 매 순간 최고의 선택이 항상 결과적으로 최적의 해를 보장할까?

답은 아니다. 하지만 그리디 알고리즘을 쓰는 이유는 그리디 알고리즘이 최적해를 보장하는 문제에서 완전 탐색, 동적 계획법보다 수행 시간이 빠르기 때문이다.

언제 써야할까?

그리디 알고리즘이 적용되는 문제는 아래 2가지 특성을 가지고 있다

• 탐욕적 선택 속성 (greedy choice property) : 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로 선택하여도 최적해를 구할 수 있음을 증명해야한다.
• 최적 부분 구조 (optimal substructure) : 부분 문제의 최적해가 전체 문제의 최적해를 만들 수 있음을 증명해야한다.

2가지 특성을 가진 문제는 그리디 알고리즘으로 해결 할 수 있다.

Greedy Algorithm 적용 방법

1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다는 장점이 있다. 이 장점으로 인해 그리디 알고리즘은 근사 알고리즘으로 사용할 수 있다.

근사 알고리즘이란?

근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화된 답을 구하지는 않지만, 비교적 빠른 시간에 계산이 가능하고 어느 정도 보장된 근사해를 계산한다.