2018년 11월 23일
그리디 알고리즘 (Greedy Algorithm)
I. 순간 최적 해 도출, 그리디 알고리즘
| 개념 | 특징 |
|---|---|
특정 순간 최적해를 구하기 위해 최적성과 효율성 개선을 통해 최적의 해를 도출하는 알고리즘 | – 최적성의 원리 – 최적 해 보장 불가 – 효율성 개선 |
II. 그리디 알고리즘 흐름도 및 수행절차
가. 그리디 알고리즘 흐름도
 |
- 최종 해 도출까지 해 선택, 과정을 반복 & 적합성 확인
나. 그리디 알고리즘 수행절차
| # | 알고리즘 | 설명 |
|---|---|---|
| ① | 해 선택 | – 부분 해 집합에 추가 다음 항목 선택 – 현재 상태 최적화 기준 만족 여부 |
| ② | 적합성 검증 | – 새로운 부분 해 집합 제약조건 여부 – 현재 집합이 해가 될 가능성 검사 |
| ③ | 해 검증 | – 신규 구성 집합이 해인지 검사 – 문제 해가 아니면 ①단계로 반복 |
- 첫 번째 선택과정에서 선택된 후 해당 항목의 선택에 대한 고려는 없으므로 거절되면 이후부터 해 집합에서 배제
III. 그리디 알고리즘 소스 구현
| #include <stdio.h> int coin[4] = {500, 100, 50, 10}; // 동전 종류 정의(주어지 문제에 따라 달라짐), 순서주의 int count[4]; int main() { int m = 860, i = 0, f = 0; // m=목표 거스름돈 while(i < 4) { // 메인 로직 – 최종해 도출까지, 동전 선택 후 반복 차감 if (coin[i] > m) i++; else if (coin[i] < m) { m -= coin[i]; // 코인 값 차감 count[i]++; } else { f = 1; count[i]++; break; } if(f) printf(“%d 원 %d 개, %d 원 %d 개, %d 원 %d 개, %d 원 %d 개 입니다.\n”, coin[0], count[0], coin[1], count[1], coin[2], count[2], coin[3], count[3]) ; else printf(“해를 구하지 못하였습니다. \n”); return 0; } |
- 동적 계획법 대비 시간적 효율성이 있으나, 최적 해 미도출의 한계로 목적에 따른 적용 필요
About The Author
