그리디 알고리즘 (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;
}
  • 동적 계획법 대비 시간적 효율성이 있으나, 최적 해 미도출의 한계로 목적에 따른 적용 필요

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^