그리디(Greedy)

그리디 알고리즘은 문제를 해결할 때 현 시점에서 가장 최선이라고 판단되는 선택(local optimum)을 반복적으로 수행하여 전체 문제를 해결하는 알고리즘 설계 기법으로, 이는 '근시안적' 인 선택을 통해 부분 최적해를 찾고, 이를 모아 전체 문제에 대한 최적해를 얻고자 하는 방식이다.

이러한 선택은 항상 전체 문제의 최적해(global optimum)를 보장하지 않기 때문에, 그리디 알고리즘이 항상 최적해를 찾을 수 있는 것은 아니다. 하지만, 특정 조건을 만족하는 문제에서 그리디 알고리즘은 적은 계산량으로 빠르고 효율적으로 최적해를 구할 수 있다.

그리디, 동적 계획법(DP), 분할 정복 간의 비교

그리디 알고리즘이 최적해를 보장하는 경우

• 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘
  • 프림(Prim) 알고리즘
  • 크루스칼(Kruskal) 알고리즘
• 메트로이드(Matroid) 구조를 만족할 때
• 허프만 코딩(Huffman Coding)

그리디 알고리즘의 적용 대상

• 최적 부분 구조(Optimal Substructure)
• 탐욕 선택 속성(Greedy Choice Property)

최적 부분 구조(Optimal Substructure)

문제에 대한 최적해가 그 하위 문제(subproblem)들의 최적해를 통해 구성될 수 있는 성질

예시: 피보나치 수열, 최단거리

탐욕 선택 속성(Greedy Choice Property)

각 단계에서 최적의 선택을 했을 때 최종적으로 최적의 해답을 구할 수 있는 경우

예시: 동전 거스름돈 문제, 활동 선택 문제

그리디 알고리즘의 절차

1. 선택 절차(Selection Procedure)

2. 적절성 검사(Feasibility Check)

   • 만족한다면 다음 단계로 넘어간다.
   • 만족하지 않으면 새로운 탐욕적 선택을 시도한다.

3. 해답 검사(Solution Check)

   • 해결되었다면 종료한다.
   • 해결되지 않았다면 새로운 탐욕적 선택을 시도한다.

더 이상 가능한 탐욕적 선택이 없거나, 문제를 해결할 수 없다고 판단되면 종료한다. 이 경우, 그리디 알고리즘으로는 문제를 해결할 수 없으므로 다른 알고리즘을 고려해야 한다.

탐욕적 선택의 불가역성

그리디 알고리즘은 탐욕적 선택이 이후의 모든 과정에서도 항상 최적임을 가정하기 때문에 일단 선택하면 이를 번복하지 않는다. 즉, 이미 선택한 것을 버리고 다른 것을 취하지 않는다.