[Algorithm] Greedy - 탐욕법

Greedy - 탐욕법

 

그리디 알고리즘은 매우 단순하면서 강력한 방법이다.

 

알고리즘의 흐름을 보면 왜 "greedy" 라는 이름이 붙었는지 알 수 있다.

 

그리디 알고리즘은 현재 상황에서 가장 좋은 최적의 해만 고르는 방법이다.

 

즉, 매 순간 제일 최적의 해로 보이는 해를 선택하며 현재의 선택이 나중에 어떠한 영향을 미칠지는 고려하지 않는다.

 

따라서 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 최적의 해만 선택해도 문제를 정상적으로 풀어낼 수 있는지 파악해야 한다. -> 그리디의 핵심!

 

예제 풀이

---

 

1. 백준 - 설탕 배달

 

문제

---

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

 

출력

---

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

제출 코드

---

sugar = int(input())
count = 0
while True:
    # 5kg 봉지로 모두 나눠 담을 수 있는가?
    if sugar%5 == 0:
        count += (sugar//5)
        print(count)
        break
    # 5kg 봉지에 정확히 나눠 담기지 않는다면 3kg 봉지를 하나 이용하여 설탕을 나눠 담는다.
    sugar -= 3
    count += 1

    # 설탕을 5, 3kg 봉지로 정확히 나눠 담을 수 없는 경우 -1을 출력한다.
    if sugar < 0:
        print(-1)
        break

 

문제풀이

---

전형적인 그리디 문제이다.

입력값의 범위는 3 <= N <= 5000 이므로 시간 복잡도를 크게 신경쓰지는 않아도 되는 문제다.

n 키로그램의 설탕을 5kg, 3kg 두 개의 봉지에 모두 나눠 담되 최소한의 봉지 개수를 사용해야하며 만일 정확히 나누어 담을 수 없을 경우에는 -1을 출력한다.

최소한의 봉지 개수를 이용하여 모든 설탕을 나눠담기 위해서는 당연히 더 많이 담을 수 있는 5kg 봉지를 최대한 많이 사용하여아한다.

따라서 5kg 봉지를 최대한 사용하는 것을 우선으로 두며 아래와 같은 알고리즘으로 코드를 작성한다.

1. while 문을 통해 무한 반복을 진행한다
2. 5kg 봉지로 모두 나눠 담을 수 있는지 확인한다 -> 나눠 담긴다면 나눠 담는데 필요한 모든 봉지 개수를 구한 후 출력한다.
3. 그게 아니라면 3kg 봉지를 하나 이용하여 현재 설탕에서 3kg을 뺀다.
4. 이를 반복하다가 만일 설탕이 음수가 되면 -1을 출력한다.

이 문제는 5kg으로 나눌 수 있을때 모두 나눠버리는 것이 제일 좋은 방법이다. 따라서 현재 상황에서의 최적의 해만 쫓는 그리디 알고리즘을 통해 최적의 해를 찾아낼 수 있다.

2. 백준 - 동전 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_arr = sorted([int(input()) for _ in range(n)], reverse=True)
count = 0
for coin in coin_arr:
    if k >= coin:
        count += (k//coin)
        k %= coin
        if k == 0:
            print(count)
            break

문제풀이

---

이 문제 또한 전형적인 그리디 문제다.

문제를 보고 아이디어를 생각해보면 바로 알 수 있듯, 최대한 큰 금액의 동전을 최대한 많이 이용해야 한다.

따라서 아래와 같은 흐름의 알고리즘을 통해 코드를 작성한다.

1. 입력받은 동전 배열을 내림차순 정렬한다. (큰 금액의 동전부터의 접근을 위함)
2. 동전 배열을 순차적으로 순회하며 목표 금액 k 보다 작거나 같은 경우, 즉 이용할 수 있는 동전 중 최고 금액의 동전을 찾은 경우 해당 동전을 최대한 사용한다.
3. 남은 동전값이 0이 되면 사용한 동전 개수를 출력한다.

이 문제 또한 동전 배열을 순회하며 최대한 높은 금액의 동전을 최대한 이용하는 것이 정답이다. 따라서 현재 상황에서 최적의 해만 고집하는 그리디 알고리즘이 최적의 해를 보장하는 유형의 문제이다.