2. 그리디 알고리즘(탐욕법)
: 선택의 순간마다 지금 당장 최적의 답을 선택하는 과정을 반복해 결과를 도출하는 방법
- 순간 가장 최선의 선택을 하는 기법이기 때문에 지역적(local)으로는 최적의 선택이지만, 이를 반복하더라도 전역적(global)로는 최적의 해가 아닐 수도 있다
- 순간마다 최선의 선택을 한 것이 전체적으로도 최선이길 기대
- 주로 문제를 분할 가능한 문제들로 분할하고, 각 문제들의 최적의 해를 구한 후 결합해 전체 문제의 최적해를 구하는 경우에 주로 사용
사용이유?
: 최적의 해를 보장할 수 없음에도, 계산 속도가 매우 빠름
이 그리디 알고리즘을 적용해 최적해를 구할 수 있는 문제 유형들은 타 알고리즘들보다 빠른 속도로 최적해를 도출할 수 있다
해결방법
1. 선택 절차: 현재 상태에서 최적의 해답 선택
2. 적절성 검사: 1에서 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사: 문제가 해결되었는지 검사, 해결되지 않았다면 -> 1 선택 절차로
활용
그리디 알고리즘을 적용해 최적해를 구할 수 있는 문제의 조건
1. 탐욕적 선택 속성(greedy choice property): 현재 선택이 이후의 선택에 영향을 주지 않음 = 탐욕적 선택이 항상 최적해를 보장
2. 최적 부분 구조(optimal substructure): 매 순간 최적의 해가 문제 전체에 대한 최적의 해여야 함 = 부분 최적해들이 모여 전체 최적해를 구할 수 있는 경우
https://it-college-diary.tistory.com/entry/21-Greedy-Algorithm탐욕법-욕심쟁이-알고리즘-개념
-> greedy 추천 문제: 풀어보면서 문제에 접근/해결하는 나만의 공식/방법을 찾아보기
