그리디(Greedy)
An algorithm that makes the optimal choice at each step.
TOC
◼︎ 그리디(Greedy)
나눌 수 있는 문제가 주어지면, “각 단계에서 지역적으로 최적의 선택이나 “탐욕적인 선택”을 하는 전략
대부분의 특성이 같은 부분 문제들로 설명될 수 있는 상황을 말한다. 따라서 대부분의 경우, 그리디 알고리즘은 재귀 알고리즘으로 구현된다.
► e.i.
상점에서 물건을 사고 남은 거스름돈을 돌려받아야 하는데, 여러 종류의 동전이 있다고 가정하자.
동전의 종류는 500원, 100원, 50원, 10원이 있다. 동전의 갯수를 최소화 하면서 거스름돈을 만들어야 한다.
이 문제를 그리디 알고리즘으로 해결하려면, 가장 큰 단위의 동전부터 최대한 많이 거슬러 줄 수 있도록 한다. 예를 들어, 거스름돈이 800원이라면 먼저 500원 동전 1개를 거슬러 준다. 그 다음으로는 100원 동전 3개를 거슬러 주면, 총 4개의 동전으로 800원을 거슬러 줄 수 있게 된다.
이렇게 각 단계에서 가장 좋은 선택을 하는 것이 그리디 알고리즘의 핵심 원칙이다.
하지만 이 알고리즘이 항상 최적의 해를 제공하는 것은 아니다. 문제의 특성에 따라 다른 접근 방식이 필요할 수 있다.
특수한 조건
그리디 알고리즘이 잘 작동하려면 두 가지 주요 조건이 충족되어야한다.
탐욕 선택 속성
이전의 선택이 이후 선택에 영향을 주지 않아야 한다.
예를 들어, 동전 거스름돈 문제에서 500원 동전을 먼저 선택하는 것이 이후의 100원, 50원, 10원 동전 선택에 영향을 주지 않는다.
최적 부분 구조
문제의 부분 해결책이 그대로 전체 문제의 해결책이 될 수 있어야 한다는 것을 의미한다.
동전 거스름돈 문제에서 이는 각 단계에서 최적의 동전을 선택하면 전체 거스름돈 문제에 대한 최적의 해결책을 얻을 수 있다는 것을 의미한다.
► 대표 문제: 설탕 배달
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
왜 그리디인가
이 문제의 경우, 봉지의 수를 최소화 하는 것이 목표이다.
이 때, 5kg 봉지는 3kg 봉지보다 많은 양의 설탕을 담을 수 있으므로, 가능 한 5kg 봉지를 많이 사용해야 한다. 따라서, 현재 상황에서 가장 좋아보이는 선택을 하는 그리디 알고리즘을 사용할 수 있는 것이다.
아까 정리한 탐욕적 선택 속성, 최적 부분 구조를 만족한다. 한 번 선택한 봉지의 종류가 다음에 선택할 봉지에 영향을 주지 않으며, 각 단계에서 최적의 봉지를 선택하면 전체 설탕 배달 문제에 대한 최적의 해결책을 얻을 수 있기 때문이다.
N이 5의 배수인 경우
설탕의 무게 N이 5의 배수인 경우, 바로 N을 5로 나눈 값을 리턴하면 된다. 는 5kg 봉지가 3kg 봉지보다 크기 때문에 최대한 많은 양의 설탕을 한 번에 배달할 수 있는 5kg 봉지를 우선적으로 사용하는 것이 봉지 수를 최소화하는 방법이기 때문이다.
N이 5의 배수가 아닌 경우
설탕의 무게 N이 5의 배수가 아닌 경우에는 조금 더 고민이 필요하다.
이 경우에는 5kg 봉지를 최대한 많이 사용하되, 그것으로 정확히 Nkg을 만들 수 없다면 3kg 봉지를 추가로 사용해야 한다. 이때, N이 5의 배수가 될 때까지 3kg 봉지를 추가로 사용해야 한다.
더이상 5kg 봉지를 사용할 수 없을 때까지 5kg 봉지를 사용하고, 남은 설탕 무게를 3kg 봉지로 채우는 것이다. 만약 남은 설탕 무게가 3의 배수가 아니라면, 정확하게 Nkg을 만들 수 없는 경우이므로 -1을 리턴하면 된다.
Snippets
나는 아래와 같이 풀었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int cnt5 = 0;
int cnt3 = 0;
cnt5 = n / 5;
int res = n % 5;
while (res >= 0) {
if (res % 3 == 0) {
cnt3 = res / 3;
break;
}
if (res == n) {
System.out.println("-1");
return;
}
cnt5--;
res += 5;
}
System.out.println(cnt3 + cnt5);
}
}
왜 설탕 배달 문제를 그리디 알고리즘으로 풀었나
그리디 알고리즘은 각 단계에서 최적의 선택을 하는 방법이다. 설탕 배달 문제의 경우, 가장 큰 봉지부터 가능한 많이 사용해야 봉지 수를 최소화할 수 있기 때문에 그리디 알고리즘을 사용했다.
추가로 DP를 사용해서 풀 수도 있다고 한다.
이후 공부할 예정인 DP는 문제를 더 작은 부분 문제로 나누고, 이 부분 문제들의 해를 결합하여 전체 문제의 해를 찾는 방법이다. DP로 설탕 배달을 풀이한다면 각각의 봉지 수를 결정하는 부분 문제로 나누고, 이 부분 문제들의 해를 결합하여 전체 봉지 수를 최소화하는 방법을 찾을 수 있다.