그리디 알고리즘 (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;
}