그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 매 선택에서 그 순간에 가장 최적이라 생각되는것을 선택하여 결과에 도달하는 방법입니다. 매 순간 가장 최적을 선택하기 때문에 현재 상황의 선택이 나중에 미칠 영향은 고려하지 않습니다. 그래서 결과를 만들었다고 해서 그것이 최적이라는 보장이 없습니다.
하지만 이 알고리즘을 적용할 수 있는 문제들은 지역적으로, 전역적으로 최적인 문제입니다.
지역적으로 전역적으로 무슨말인지 헷갈리시다면 위 그림을 보시면 바로 이해가 가능합니다.
왼쪽 그림은 최소값을 찾는다고 가정했을때 지역적으로, 전역적으로 최적인 답을 만족하는 그래프의 형태이고
오른쪽 그림은 지역적으로는 최적인 답을 찾을 수 있지만, 전역적으로는 최적인 답이 아닙니다.
그래서 문제를 접하면 왼쪽그래프 형태와 같이 지역적,전역적으로 최적인 문제인가, 현재 상황에서 최적의 답만 선택해도 풀 수 있는지 파악하셔야 합니다.
그리디 알고리즘으로 푸는 문제는 대부분 탐욕스런 선택 특성(greedy choice property) 과 최적 부분 구조 조건(optimal substructure)이라는 두가지 조건이 만족됩니다. 탐욕스런 선택 조건은 앞의 선택이 미래의 선택에 영향을 주지 않는것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해라는 것 입니다.
또 이 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제를 접할 때 '큰 순서, 작은 순서'와 같은 기준을 문제에 내포시킵니다. 그래서 정렬 알고리즘과 주로 짝을 맞추어서 나오기 때문에 정렬하는 다양한 방법(Comparator, 우선순위 큐 등) 들을 공부하시면 문제 푸는데 도움이 될 겁니다.
참고 - 위키백과
'알고리즘 정리' 카테고리의 다른 글
| 다익스트라 알고리즘(Dijkstra Algorithm) - JAVA (3) | 2022.03.23 |
|---|---|
| [백준 2110] - 공유기 설치 (JAVA) + Parametric search 알고리즘 (0) | 2022.02.23 |
| [백준 16236] - 아기상어(JAVA) (0) | 2022.01.09 |
| 백트래킹(Backtracking) 알고리즘 - JAVA (0) | 2022.01.04 |
| "투 포인터 알고리즘" + [백준] 2003 - 수들의 합 2(JAVA) (0) | 2021.12.31 |