욕심과 실패..그것이 그리디의 길..⭐

📖 그리디 알고리즘이란?

✅ Greedy Algorithm = 탐욕적 알고리즘
✅ 매 선택에서 지금 이 순간 당장의 최적인 답을 선택
(나무위키, 그리디 알고리즘)

ㄴ 당장의 최선 ≠ 전체적 최선일 수 있음

ㄴ 항상 최선을 보장하지 못함

---

1. local minimum vs global minimum

그리디 알고리즘의 가장 중요한 포인트는 바로 이 부분이다.
그리디 알고리즘은 매 순간 당장의 최선의 답을 선택하기 때문에, 편협한 결정을 내릴 수 있다.
(= 욕심이 끝이 없다가 같은 실수 반복 구간 두둥!)

아래와 같은 그래프에서 최소값을 찾는다고 가정해보자.

가로축이 0.7인 부분에서 출발하여 그리디 알고리즘을 사용하면 다음과 같은 과정을 거친다.

• 0.7 부분을 기준으로 왼쪽, 오른쪽 중 더 감소하는 방향으로 움직인다.(위 그래프에서는 오른쪽)
• 더 이상 작은 값으로 움직일 수 없을 때까지 위를 반복한다.
• 최종 최소값을 선택한다.(위 그래프에서는 local minimum 위치)

그리디 알고리즘은 당장 감소하는 방향으로만 움직이기 때문에 증가 구간을 거쳐야 도달할 수 있는 global minimum을 구하지 못한다.
위 그래프에서는 최대값을 구할 때에도 0.7 지점에서 출발한다면 local maximum을 최댓값으로 선택,
감소 구간을 거쳐야 도달할 수 있는 global maximum을 구하지 못한다.

---

2. 그리디 알고리즘 활용

• 그리디 알고리즘을 사용하기 전에, 해당 문제가 그리디 알고리즘으로 해결 가능한 지를 판단하는 것이 중요하다.
• 위 그래프와 같이 탐욕적 방법으로 도달할 수 없는 지점이 있는 경우에는 그리디 알고리즘을 사용하면 안된다.
• 하지만 무조건 큰 값, 무조건 긴 값, 무조건 작은 값, 무조건 짧은 값을 구하여 문제를 풀 수 있는 경우 그리디 알고리즘을 사용하면 최적의 해 도출이 보장된다.
• 그리디 알고리즘 + 정렬 = 크루스칼 알고리즘 = 모든 간선을 정렬한 후 짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘

ㄴ 늘 최적의 해를 보장하지 못함 = 사용 판단 중요

ㄴ 그리디로 풀 수 없다면, 동적 계획법(Dynamic Programming) 활용