Greedy Algorithm (탐욕 알고리즘)

- 최적화 문제 풀이에 쓰임 (= 최대값 or 최소값 구하기)

- 현재 시점에서 최적이라고 생각되는 값을 선택하는 알고리즘.

하지만 전체 시점에서 추출된 해가 항상 최적이라는 보장이 없다.

 

* 풀이 단계

1. 해 선택

 : 가장 좋은 해 선택

2. 실행 가능성, 해 검사

 : 선택한 해가 조건을 충족하는지 확인.

 충족하지 않을 경우, 1번의 해에서 값을 수정한 뒤 다시 반복

 

* EX) 동전 거스름 돈 문제

[CASE1]

800원의 거스름돈을 500, 100 원 동전을 사용하여 줄 수 있는 최 소 동전의 갯수 구하기

  1) 제일 적은 갯수로 주기 위해 가장 큰 금액의 동전 (500)을 선택.
  2) 나머지 금액 (800-500) 은 100원 짜리 동전을 사용
  ==> 답: 4개 (500원 1개 , 100원 3개)

--> 이 방식으로 구한 해가 항상 최적의 해를 보장하진 않는다.

 

[CASE2]

800원의 거스름돈을 500, 400, 100 원 동전을 사용하여 줄 수 있는 최 소 동전의 갯수 구하기

그리디알고리즘으로 구한 해는 4개 이지만,
실제 최적 해는 2개 (400원 2개) 이다.

 

 

---

[참고] https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 

SW Expert Academy