학습 일자 : 2023.04.22

Greedy Algorithm (탐욕법)

현재 상황에서 가장 좋은 것을 고르는 알고리즘

탐욕 알고리즘은 현 상황에서 가장 좋은 방법을 우선적으로 수행하기 때문에 언제나 최적의 해를 구하는 것은 아님 (동적 계획법은 최적의 해를 구하기 때문에 동적 계획법보다는 덜 효율적임)

탐욕 알고리즘 과정

1. 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤 이를 부분해 집함에 추가한다
2. 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지를 확인한다. (문제의 제약 조건을 위반하지 않는지를 검사하는 과정임)
3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면, 1번 해 선택부터 다시 시작한다.

[탐욕 알고리즘 과정 예시]

| <편의점 점원의 거스름돈 줄이기> ❓거스름돈을 줄 때 어떻게 하면 손님에게 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?

만약, 손님이 1,200원짜리 물건을 구매하고 2,000원을 지불했다면, 거스름돈으로 다음과 같이 줄 수 있다. 1. 10원 x 80 2. 100원 x 8 3. 500원 x 1 + 100원 x 3
⇒ 거스름돈을 3번으로 줄 때 돈전의 개수를 가장 최소한으로 사용할 수 있음.

1. 해 선택 : 현 단계에서 가능한 가장 큰 단위를 선택함.
2. 실행 가능성 검사 : 가장 큰 단위로 거스름돈이 지불 가능한지 확인
3. 해 검사 : 거스름돈이 남아 있는지 확인, 남아 있으면 다시 1번(해선택)으로 돌아감 | | --- | | <탐욕 알고리즘으로 구현한 거스름돈 계산 프로그램> 👩‍💻 [소스 확인하기] |

⇒ 탐욕 알고리즘이 언제나 최적의 상황으로 나오는 것은 아님!

만약, 400원짜리 동전이 새로 나온다면, (500원 x 1 + 100원 x 3)보다는 (400원 x 2)가 가장 최적의 해이다. (동전의 개수가 가장 적음).

하지만, 탐욕 알고리즘을 사용한다면 결과는 언제나 (500원 x 1 + 100원 x 3)으로 나올 것이다. 동전의 종류가 500원, 400원, 100원… 이렇게 있는 상황에서 가장 좋은 것(=가장 큰 단위)는 500원이기 때문에 500원을 먼저 체크할 것이기 때문이다.

크루스칼의 최소 신장 트리 알고리즘