그리디(Greedy)
- 그리디 알고리즘은 최적의 해를 구하기 위해 사용되는 근시안적인 방법론으로 '각 단계에서 최적이라고 생각되는 해를 선택'하는 방식으로 전체 단계를 진행하여 최종적인 해에 도달하는 알고리즘이다.
- '전체 문제를 부분 문제로 쪼개고, 부분 문제의 해를 통합해 전체 문제의 해를 구한다'는 점에서 완전 탐색 및 동적 프로그래밍과 유사하다. 하지만 각 단계에서 모든 선택지를 고려해보는 다른 두 방법과는 달리, 그리디는 각 단계에서 최적의 선택지만을 고려한다.
- 따라서 그리디는 전체 문제에 대한 최적해를 보장하지는 않지만, 최적해의 근사치를 보다 빠른 속도로 구할 수 있으며, 경우에 따라 최적해를 구할 수도 있다.
그리디 알고리즘의 정당성 증명
- 알고리즘 문제는 대부분 최적해의 근사치가 아닌, 최적해를 찾아야한다. 때문에 그리디 알고리즘을 통해 문제를 해결하기 위해서는 '해당 문제가 그리디 알고리즘으로 최적해의 근사치가 아닌, 최적해를 찾을 수있다'는 것을 보장해야한다.
- 그리디 알고리즘을 통해 최적해를 구할 수 있다는 것을 보장하기 위해서는 탐욕적 선택 속성, 최적 부분 구조를 만족해야한다.
탐욕적 선택 속성(Greedy Choice Property)
- 탐욕적 선택 속성이란 '각 단계에서 탐욕적 선택을 했을 때, 전체 문제에 대한 최적해를 구할 수 있다'는 것을 의미한다.
- 즉 각 단계에서 모든 선택지를 고려하지 않고 탐욕적 선택을하더라도 결국 전체적으로 최적의 결과를 가져온다는 것이다.
최적 부분 구조(Optimal Substructure)
- 최적 부분 구조란 '전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있다'는 것을 의미한다.
- 즉 부분 문제의 최적해들을 조합하여 전체 문제의 최적해를 구할 수 있다는 것이다.
그리디 알고리즘 적용 단계
- 선택 절차 정의
- 문제의 구조에 맞게 선택 절차를 정의한다. 특정 기준에 따라 선택지들을 정렬하는 것을 의미한다.
- 적절성 검사
- 각 단계에서 첫 번째 선택지부터 선택 가능한 상황인지 판단한다. 선택 불가능한 경우 다음 선택지로 넘어가서 다시 판단한다.
- 해답 검사
- 모든 단계의 선택이 완료되면, 모든 단계의 선택지들의 조합으로 전체적인 해답이 구해졌는지 판단한다.