그리디 알고리즘
- 현재 상황에서 가장 좋은 것을 고르는 알고리즘
- 현재 상황에서 가장 좋은 결과가 최종 결과의 최적해를 보장해주는 것은 아니다.
=> 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않는다.- 기준을 따라 현재 상황에서 가장 좋은 것을 선택하는 알고리즘
=> 문제에서가장 큰 순서대로,가장 작은 순서대로같은 기준을 제시해 준다.
=> 대체로 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 정렬 알고리즘과 자주 짝을 이뤄 출제된다.
- 기준을 따라 현재 상황에서 가장 좋은 것을 선택하는 알고리즘
가장 큰 수 찾기
출처 : https://velog.io/@contea95/탐욕법그리디-알고리즘
최종적인 최적해는 노란색 선을 따라서 탐색하는 것이지만 그리디를 사용할 경우 빨간색 선을 따라 탐색하게 된다.
가장 첫 번째 탐색에서는 17이 6보다 크기 때문에 당장 최적의 선택이지만 다음 탐색에 가서도 그렇다고 보장할 수 없다.
그리디 알고리즘 조건
항상 안전하다는 것이 보장되어야 한다.
- 안전하다 ⇒ 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다.
- 안전하지 않은 경우 위의 가장 큰 수 찾기 처럼 최적해를 보장할 수 없기 때문에
최적 부분 구조 조건
- 문제의 최종 해결 방법이 부분 문제의 최적 해결 방법이어야 한다.
- 값들이 서로 영향을 주면 안된다.
