Greedy Algorithm에 대해 설명해보세요.

---

그리디 알고리즘이란?

• 탐욕법이라고도 불리며, 뒤의 선택은 고려하지 않고, 현재 상황에서 최적의 선택을 하는 방식으로 진행하여 문제를 해결하는 방법이다.

• 찾은 정답이 항상 최적해를 보장하지 않지만 빠르게 문제를 해결할 수 있다.

---

그리디 알고리즘의 정당성

• 최적해를 보장하기 위해서 만족해야 하는 두 가지 조건이 있다.

  • 탐욕적 선택 속성(Greedy Choice Property)
    : 탐욕적인 선택이 이후의 선택에 영향을 주지 않고, 최적해여야 한다.

  • 최적 부분 구조(Optimal Substructure)
    : 부분 최적해를 모아 전체 최적해를 구할 수 있다.

• 위의 조건들을 만족하는 구조를 매트로이드 구조라고 한다.

---

그리디 알고리즘의 작동 방식

1. 선택 절차(Selection Procedure)
: 현재 상태에서의 최적의 해를 선택한다.

2. 적절성 검사(Feasibility Check)
: 선택한 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사(Solution Check)
: 기존의 문제가 해결됐는지 확인하고, 그렇지 않다면 선택 절차로 돌아가 과정을 반복한다.

---

그리디 알고리즘의 활용

• 항상 최적의 해를 주진 않지만 특정 상황에서는 주기도 하며, 최적해가 아닌 근사치를 구하는 것이 목표일 때 사용되기도 한다.

• 대표적인 알고리즘으로는 프림 알고리즘(Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm), 그리고 다익스트라 알고리즘(Dijkstra Algorithm) 등이 있다.

• 대표적인 예제로는 거스름돈 문제, 활동 선택 문제, 분할 가능 배낭 문제 등이 있다.

---

결론

그리디 알고리즘은 탐욕법이라고도 하며, 매 순간 최적의 선택을 하면서 문제를 해결하는 방식의 알고리즘입니다. 항상 최적해를 찾는다는 보장은 없지만 근사치를 구하고자 할 때 빠르게 찾을 수 있습니다. 최적해를 찾기 위한 문제 조건에는 탐욕적 선택 속성과 최적 부분 구조 두 가지가 있습니다. 탐욕적 선택 속성은 현재의 선택이 이후에 영향을 미치지 않는 최적의 선택이어야 하며, 최적 부분 구조는 전체 최적해가 부분 최적해로 구성되어 있는 것입니다. 대표적으로 다익스트라 알고리즘에 활용되며, 거스름돈 문제, 분할 배낭 문제 등의 해결 방법으로 사용되기도 합니다.