참고
그리디 알고리즘
NOTE
탐욕 알고리즘 ⇒ “매 선택에서 현재 당장 최적인 답”을 선택해 정답을 도출하는 알고리즘!
20 → 3 → 1이 정답이지만, 20 → 2 → 10을 선택하게됨
•
현재의 기준으로 최선의 선택을 해결하므로, 언제나 전체적인 최적의 결과를 가져오지는 않는다.
•
한 번 선택한 이전단계를 다시 고려하지 않고(백트래킹 하지않음) 각 단계에서 최선의 선택을 선택하여 정답을 찾는다.
탐욕 알고리즘의 조건
NOTE
탐욕 알고리즘은 항상 최적의 해를 구하지 않기 때문에 특정 조건이 필요하다!
1.
탐욕 선택 속성
•
이전의 선택이 이후에 영향을 주면 안된다!
2.
최적 부분 구조
•
부분 문제의 최적 결과가 전체에도 그대로 적용되어야 한다.
예시 - 활동 선택
NOTE
N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때 최대한 많이 할 수 있는 활동의 수 구하기
최대한 많은 활동을 해야하므로, 종료시간이 빠른 것 부터 선택
예시 - 거스름돈 문제
NOTE
돈을 낸 뒤, 거스름돈을 최소 개수의 동전 및 지폐의 조합으로 받을 때, 그 개수를 구하는 방법
public class _11047 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String[] s;
String[] temp = br.readLine().split(" ");
int N = Integer.parseInt(temp[0]);
int K = Integer.parseInt(temp[1]);
Integer[] money = new Integer[N];
for (int i = 0; i < N; i++) {
money[i] = Integer.parseInt(br.readLine());
}
int answer = 0;
Arrays.sort(money, Comparator.reverseOrder());
for (int i = 0; i < money.length; i++) {
if(K >= money[i]){
answer += K/money[i];
K %= money[i];
}
}
System.out.println(answer);
}
}
Java
복사
•
하지만 이 경우는 언제나 적용이 가능하지 않음
◦
ex) 거스름돈 120원, 동전종류(50원, 40원, 10원)
▪
MSD → 50원 2개, 10원 2개
▪
실제정답 → 40원 3개
◦
50원과 40원의 선택은 독립적으로 연관되지 않기 때문