그리디 (Greedy Algorithm)
- 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘
- 현재 상황에서 가장 좋아보이는(즉, 최적이라고 생각되는) 선택을 반복하여 전체 문제의 최적해를 찾는 알고리즘
- 대표적인 문제 유형
- 거스름돈 문제: 최소한의 동전 개수로 거스름돈을 만드는 문제
- 회의실 배정 문제: 가장 많은 회의를 진행할 수 있도록 선택하는 문제
- 배낭 문제(Fractional Knapsack): 무게당 가치가 높은 순서대로 담는 문제
- 주의사항
- 모든 문제에서 최적해를 보장하지 않는다.
- 동적 프로그래밍(DP)과 비교하여 사용 여부 결정
- 반례가 없는지 철저히 검토해야 함
- 모든 문제에서 최적해를 보장하지 않는다.
그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등으로 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기법이 함께 사용되는 경우가 많다. 대표적인 예시로 크루스칼(Kruskal) 알고리즘으로 모든 간선을 정렬한 이후에 짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘이 있다.
핵심 아이디어
- 전체 최적해(Global Optimum)를 위해, 각 단계에서의 지역 최적해(Local Optimum)를 선택
- 한번 선택한 해는 다시 변경하지 않음 (-> 탐욕스럽게, 되돌아보지 않음)
성립 조건
그리디 알고리즘이 정답을 보장하는 조건은 다음과 같다:
아래의 두 조건을 만족하지 않으면, 그리디는 근사해는 구해줄 수 있어도 정답을 보장하지 않는다.
- 탐욕 선택 속성(Greedy Choice Property)
- 전체 최적해(optimal solution)는 각 단계의 최적해들을 통해 얻을 수 있어야 함.
- 최적 부분 구조(Optimal Substructure)
- 문제의 전체 해가 부분 문제의 최적해로 구성될 수 있어야 함.
예시: 거스름돈 문제
우리가 흔히 거스름 돈을 줄 때 가장 적은 양의 화폘르 주는 것이 제일 편하다.
예를들어 1260원을 거슬러주어야 할 때, 500 * 2 + 100 * 2 + 50 * 1 + 10 * 1으로 6개의 동전을 거슬러주면 된다.
이처럼 무조건 큰 화폐 단위를 거슬러 준다는 알고리즘만 지키면 최적의 해를 보장할 수 있다.
💻 코드
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int result = 0;
// 그리디 적용: 큰 단위의 동전부터 사용
result += n / 500;
n %= 500;
result += n / 100;
n %= 100;
result += n / 50;
n %= 50;
result += n / 10;
n %= 10;
System.out.println(result);
scanner.close();
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int price = scanner.nextInt();
int[] coins = {500, 100, 50, 10, 5, 1};
int count = 0;
// 거스름돈을 큰 동전부터 사용해 최소 개수 계싼
for (int coin : coins) {
count += price / coin; // 해당 동전으로 줄 수 잇는 개수
price %- coin; // 남은 거스름돈
}
System.out.println(count);
}
}Reference
Good Luck!