정의
•
현재 상태에서 선택할 수 있는 방법 중 최선의 선택을 하다 보면 전체 문제에 대한 최선의 선택지가 나올 거라고 가정하는 알고리즘
•
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정
특징
•
각 단계에서 선택한 값이 전체를 아우렀을 때 항상 최적의 해를 보장하진 않음
◦
그리디로 풀었을 때 최적의 해 도출할 수 있는 문제가 있고, 아닌 문제가 있기에 문제 풀기 전에 그리디로 풀어도 되는지 안되는지 먼저 판단해야 함.
과정
1.
해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2.
적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3.
해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사
•
전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복
예시
백준 11047_동전 사용해서 k원 만드려 할 때 필요한 동전 개수의 최댓값
•
내 풀이) k=4200원, 동전=1,5,10,50,100,500,1000,5000,10000,50000
◦
4200원보다 보다 작은 수 중 최대값은 1000원이므로
▪
1000원짜리 동전으로 최대한 4200원에 가깝게 구성해보기
•
1000원 * 4개 → 남은 돈 : 200원
◦
200원보다 작은 수 중 최대값은 100원이므로
▪
100원짜리 동전으로 최대한 200원에 가깝게 구성해보기
•
100 * 2개 → 남은 돈 : 0원 (문제 해결!)
•
내 풀이가 그리디인 이유)
◦
동전을 최소로 쓰려면 큰 액수의 동전부터 먼저 사용해야 한단 점이 최선이라는 점에 착안해서,
◦
현재 남은 금액을 동전으로 채우기 위해 매번 가장 큰 액수의 동전을 고르는 최선의 행동을 함.
•
내 풀이를 그리디 과정에 대입해보자면면)
1.
해 선택 : 현재 남은 금액을 채울 수 있는 가장 큰 액수의 동전 고르기 (1000원)
2.
적절성 검사 : 고른 동전을 몇 개 사용할 지 정하기 (4개)
3.
해 검사 : 현재 남은 금액이 0원인지 확인하기 (200원 남음)
•
전체 문제 해결하지 못했다면 1번부터 다시 반복 (남은 금액 0원 될 때까지 반복)
•
이 문제에 그리디를 쓸 수 있는 이유)
◦
동전들이 배수의 형태로 주어지기 때문에
▪
200원 2개보단 400원 짜리 1개가 더 의미 있음
•
항상 해가 존재하는 이유) 해가 없다면 예외 처리 해주기
◦
1원짜리 동전이 항상 존재해서
▪
주어진 동전들로 주어진 금액 k를 못 만드는 경우가 절대 나오지 않기 때문임
코드
private static int solution(int k) {
int count = 0;
int idx = numbers.length - 1;
while (k != 0) { // 3. 해 검사 -> 무조건 k=0이 되는 순간이 있기에 가능 (1원이 존재해서)
while (numbers[idx] > k) { // 1. 해 선택
idx--;
}
count += (k / numbers[idx]); // 2. 적절성 검사
k -= numbers[idx] * (k / numbers[idx]);
}
return count;
}
Java
복사
참고