.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
정의
•
지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출
중요사항
•
정당성 분석이 중요
•
계산 속도가 빠르다.
•
가장 큰 값을 우선적으로 선택해서 도출한다.
•
종합적인 결과에 대해서는 최적의 해를 보장할 수 없다.
(지역적(local)으로는 최적의 선택이지만 이를 반복해도 전체적(global)으론 최적의 해가 아닐 수 있음)
주요 속성
1. 탐욕 선택 속성(Greedy Choice Property)
•
각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
2. 최적 부분 구조(Optimal Substructure)
•
전체 문제의 최적해가 ‘부분 문제의 최적해로 구성’될 수 있는 경우
•
→ 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것
알고리즘 단계
1.
문제의 최적해 구조를 결정
2.
문제의 구조에 맞게 선택 절차를 정의 : 선택 절차(Selection Procedure)
•
현재 상태에서의 최적 결정을 진행
•
선택 변동 X
3.
선택 절차에 따라 선택을 수행.
4.
선택된 해가 문제의 조건을 만족하는지 검사 : 적절성 검사(Feasibility Check)
•
선택 항목이 ‘문제의 조건’을 만족시키는지 확인
•
조건이 만족하지 않으면 해당 항목은 제외
5.
조건을 만족하지 않으면 해당 해를 제외
6.
모든 선택이 완료되면 해답 검사 : 해답 검사(Solution Check)
•
모든 선택이 완료되면 ‘최종 선택’이 문제의 조건을 만족시키는지 확인
7.
조건을 만족하지 않으면 해답으로 인정X
출제 문제 종류
•
거스름돈 문제 : 가장 적은 동전 수를 거스르는 문제
•
간단한 문제로 출제될 가능성 큼
•
시간 복잡도 : O(N)
동적 계획법과의 비교
분류 | 그리디 알고리즘(Greedy Algorithm) | 동적 계획법(DP: Dynamic Programming) |
설명 | 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식 | 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식 |
성립 조건 | 1. 탐욕 선택 속성(Greedy Choice Property)
2. 최적 부분 구조(Optimal Substructure) | 1. 중복 부분 문제 (Overlapping Subproblems)
2. 최적 부분 구조 (Optimal Substructure) |
중복 부분 문제 | 중복 부분 문제를 해결하지 않습니다. | 중복 부분 문제를 해결할 수 있습니다. |
상황 | - 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구합니다.- 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있습니다. | - 모든 상황을 계산하여 최적의 경로를 구할 수 있습니다- 모든 상황을 계산하기에 시간이 오래 걸립니다. |
