week6.md

WEEK 6: 그리디 알고리즘

그리디 알고리즘(Greedy Algorithm, 탐욕 알고리즘)

최적의 값을 구해야 하는 상황에서 사용됨
근시안적인 방법론으로 각 단계에서 최적이라고 생각되는 것을 선택 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘.
항상 최적의 값을 보장하는것이 아니라 최적의 값의 근사한 값을 목표
주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용

• 근시안적 방법론: 단기적인 목표를 중심으로 한 전략적인 접근 방법을 의미. 이 방법론은 주로 현재의 문제를 해결하는 데 초점을 맞추며, 장기적인 전망보다는 단기적인 성과를 중요시함
  
• 근사 알고리즘(Approximation Algorithm): 최적의 해를 구할 수 없는 문제에서 근사한 해를 구하는 알고리즘. 근사 알고리즘은 항상 최적해를 보장하지는 않지만, 많은 경우에는 최적해에 근접한 값을 구할 수 있음
• 예를 들어, 노드에서 가장 합이 높은 방법을 선택하는 경우 -> 각각 상황에서 '최적'이라고 생각하는 방법을 선택 (상황에서 가장 높은 수를 선택하기)
  

그리디 알고리즘 주요 속성

2가지 조건이 성립해야 그리디 알고리즘 사용 가능

1. 탐욕 선택 속성(Greedy Choice Property)
   • 각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
   • 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것
2. 최적 부분 구조(Optimal Substructure)
   • 전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우
   • 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미

그리디 알고리즘 단계

1. 문제의 최적해 구조를 결정
2. 문제의 구조에 맞게 선택 절차를 정의 : 선택 절차(Selection Procedure)
   • 현재 상태에서 가장 최적인 선택을 수행
3. 선택 절차에 따라 선택을 수행
4. 선택된 해가 문제의 조건을 만족하는지 검사 : 적절성 검사(Feasibility Check)
   • 선택한 항목이 문제의 조건을 만족시키는지 확인
5. 조건을 만족하지 않으면 해당 해를 제외
6. 모든 선택이 완료되면 해답을 검사 : 해답 검사(Solution Check)
   • 모든 선택이 완료되면, 최종 선택이 문제의 조건을 만족시키는지 확인
7. 조건을 만족하지 않으면 해답으로 인정되지 않음

DP(동적 계획법)와 비교

• DP와 달리 중복 부분 문제를 해결 X
• DP는 모든 상황을 계산하여 최적의 경로를 구하기에 시간이 오래 걸리지만, 탐욕 알고리즘은 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구함

References

• https://adjh54.tistory.com/212