5. 그리디 알고리즘(Greedy Algorithm)

✅ 그리디 알고리즘이란?

 

 ㅇ 그리디 알고리즘은 탐욕 알고리즘이라고 불리며, 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

 

 ㅇ 주로 최적해를 구하는데에 사용되는 방법이며, 속도가 빠르다는 장점이 있다.

 

 ㅇ 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행된다.

   - 순간마다 하는 선택은 그 순간에 대해서는 지역적으로 최적이지만, 최종적(전역적)으로는 최적이라고 보장할 수 없다.

 

 ㅇ 특성을 가지는 문제들을 해결하는데 강점이 있는 알고리즘으로, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다.

 

✅ 그리디 알고리즘을 적용하기 위한 조건

 

 1️⃣ 탐욕적 선택 속성 ( Greedy Choice Property )

 

   - 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.

 

 2️⃣ 최적 부분 구조 ( Optimal Substructure )

 

   - 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결방법으로 구성된다. 

 

✅ 그리디 알고리즘 문제를 해결하는 순서

 

 1️⃣ 선택 절차 ( Selection Procedure )

  

   - 현재 상태에서의 최적의 해답을 선택한 뒤 이를 집합에 추가한다.

 

 2️⃣ 적절성 검사 ( Feasibility Check )

   

   - 선택된 해가 문제의 조건을 만족하는지 검사한다.

  

 3️⃣ 해답 검사 ( Solution Check )

 

   - 새로운 부분해 집합이 문제의 해가 되는지 검사한다.

   - 만약 문제의 해가 완성되지 않았다면, 1번 선택 절차부터 다시 시작한다.

---

- 예시1

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

test_case, money = map(int, input().split())
coin_list = []
count = 0
for i in range(test_case):
    coin_list.append(int(input()))
    
coin_list.reverse()
for i in coin_list:
    print("현재 남은 돈 : ", money)
    if money >= i:
        count += money // i
        money = money % i
        if money <= 0:
            break
print(count)

 

 해당 문제는 주어진 금액을 몇 개의 동전으로 만들어낼 수 있는지를 판단하는 문제이다.

 

1. 처음에 입력은 동전의 개수(test_case)와 가치의 합(money)를 받아냅니다.

2. 동전의 갯수(test_case) 만큼 반복문을 통하여 리스트에 넣어줍니다.

3. 가장 큰 동전부터 테스트를 해야 하므로 reverse() 함수를 통하여 리스트를 역으로 전환시켜줍니다.

 - [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000] -> [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1]

4. 이제 역으로 전환된 리스트의 값이 주어진 가치의 합(money) 보다 크다면, 나눈 값만큼 count를 추가해주고 가치의 합(money)은 나눈 값의 나머지로 저장해줍니다.

5. 4번의 과정을 가치의 합(money)이 0보다 클 때까지 반복해줍니다.

 

 

- 예시 2

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

 

money = int(input())
money_list = [500, 100, 50, 10, 5, 1]

result_money = 1000-money
sum = 0

for i in money_list:
    print("현재 남은 돈 : ", result_money)
    if result_money >= i:
        sum += result_money // i
        result_money = result_money % i 
        if result_money <= 0:
            break
print(sum)

 

 해당 문제는 동전이 500엔, 100엔, 50엔, 10엔이 충분히 주어져 있다.

또한, 물건을 사고 1000엔 지폐 한 장을 냈을 때 (1000엔-주어진 금액)에 대한 잔돈의 개수를 파악하는 문제이다.

 

1. 물건의 가격(money)과 동전의 리스트(money_list)를 작성한다.

2. 1000엔 지폐 한장을 내는 상황이므로 1000엔 - 물건의 가격을 변수(result_money)에 저장한다.

3. 잔돈(result_money)이 리스트의 동전보다 클 경우 사용되는 동전의 개수와 남은 잔돈을 계산한다.