그리디 알고리즘(Greedy Algorithm)

1. 그리디 알고리즘이란?

그리디 알고리즘 :  "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

 

예를 들어 위 그림에서 0부터 시작해 아래로 내려가며 요소의 수를 더해 가장 큰 결과를 만들어야 하는 문제가 있다고 할 때

그리디 알고리즘은 순간마다 최적의 해답을 찾기 때문에 처음 시작인 0에서 1보다 9가 큰수이기 때문에 9를 선택한다.

이후 9인 지점에서 12와 16중에 큰수인 16을 선택하여 최종 결과는 9+16으로 25가 된다.

하지만 실제 가장 큰 수를 만들수 있는 경로는 1을 거쳐 99로 가는 것이다.

이처럼 문제해결에서 그리디 알고리즘으로 해결 할 수 없는 문제에 그리디 알고리즘을 적용한 경우에는 최적해를 보장해주지 못한다.

---

2. 어떤 경우에 적합한가?

• 탐욕 선택 속성(greedy choice property)

한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해만 구하여 전체 문제에 대한 최적해를 구할 수 있다는 의미이다.

 

• 최적 부분 구조(optimal substructure)

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

이 속성을 만족하면 "최적 부분 구조를 갖는다."라고 한다.

반대로, 부분 문제들의 최적해만으로 전체 최적해를 얻을 수 없는 경우 "최적 부분 구조를 갖지 않는다."고 한다.

예를 들자면 피보나치 수열을들 수 있다.

f(n) = f(n-1) + f(n-2)

위 수식에서 f(n-1)은 다시 f(n-2) + f(n-3)이 되고 이러한 작은 부분 문제들이 연속되어 큰 문제인 피보나치 수열을 풀 수 있다.

 

그리디 알고리즘은 위 두 조건을 만족하는 특성을 가지는 문제들을 해결하는데 강점이 있다.

---

3. 그리디 알고리즘을 활용한 문제 풀이(Python)

그리디 알고리즘으로 풀어야 하는 대표 문제로 거스름돈 문제가 있다.

거스름돈 문제와 비슷한 문제가 있어 그리디 알고리즘 적용 예시를 들어보려한다.

문제 출처 : https://www.acmicpc.net/problem/11047

11047번: 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

풀이 코드

n, k = map(int, (input().split()))
coin = []
cnt = 0
for i in range(n):
    coin.append(input())
for j in range(n-1, -1, -1): #greedy : 가장 큰 단위부터 시작 하는것이 이득
    if int(coin[j]) <= k : #선택된 동전이 현재 목표치보다 작거나 같은경우
        cnt += k // int(coin[j]) #선택된 동전을 몇개 사용해야 하는지 계산
        k -= (int(coin[j]) * (k // int(coin[j]))) #현재 목표치에서 변환된 값을 차감
    else :
        cnt = cnt
print(cnt)

풀이 과정

이 문제는, 매 순간 가장 탐욕적인 선택을 하는 그리디 알고리즘을 활용한 문제이다.

목표치의 액수 k = 12500원 이고 동전의 종류 coin = [100, 500, 1000, 5000, 10000]인 경우

최소갯수의 동전으로 목표치를 달성하기 위해선 항상 목표액수보다 작거나 같은 동전중 가장 단위가 큰 동전을 사용해야한다.

먼저 10000원짜리 동전을 하나 사용하고 남은 2500원은 2500보다 작거나 같고 보유한 동전중 가장 단위가큰 1000원 짜리 동전2개

이후 남은 500원은 500원짜리 동전하나 사용하여 총 4개의 동전을 사용하면 된다.

참고로 동전의 종류로 표현된 coin은 Python의 List이므로 가장 첫번째 요소의 인덱스가 0부터 시작되는것과

for x in range(i, j, k)

위 코드와 같은 Python 반복문에서 i 부터 j까지 k만큼의 간격으로 루프를 돈다. j는 exclusive한 특징이 있다는것도 기억하자.