핵심
NOTE
•
매 선택에서 현재 당장 최적의 답을 선택해 결과를 도출하는 방법
내용
1. 그리디 알고리즘은 무엇인가?
NOTE
•
매 선택에서 현재 당장 최적인 답을 선택해 전체 적합한 결과를 도출하자는 기법
◦
백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않음!
→ 전체에서 최적값을 언제나 구할 수는 없다!
•
전체의 경우 10 → 1의 경우로 11이 나와야 한다
•
그리디 알고리즘의 경우 1 → 150으로 151이 나오게됨
NOTE
•
하지만 그럼에도 불구하고 속도가 매우 빠르기 때문에 자주 사용된다.
•
하지만 항상 최적해가 되지않으므로 특수한 조건이 만족되어야함
◦
탐욕 선택 속성 (Greedy Choice Property)
▪
이전의 선택이 이후에 영향을 주지 않아야 한다
◦
2. 그리디 알고리즘 예시(선례) - 활동 선택
NOTE
•
N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때 최대한 많이 할 수 있는 활동의 수 구하기
•
최대한 많은 활동을 해야하므로, 종료시간이 빠른 것 부터 선택
•
종료시간을 기준으로 정렬, 제일 먼저 끝나는 활동 선택하고 다음 활동 찾는 수행
List<Action> list = new ArrayList<>();
list.add(new Action("A", 7, 8));
list.add(new Action("B", 5, 7));
list.add(new Action("C", 3, 6));
list.add(new Action("D", 1, 2));
list.add(new Action("E", 6, 9));
list.add(new Action("F", 10, 11));
Collections.sort(list);
List<Action> result = greedy(list);
for (Action action : result) {
System.out.println(action.toString());
}
Java
복사
3. 그리디 알고리즘 예시(반례) - 거스름돈 문제
NOTE
•
돈을 낸 뒤, 거스름돈을 최소 개수의 동전 및 지폐의 조합으로 받을 때, 그 개수를 구하는 방법
◦
ex) 2730원 물건을 5000원으로 결제 → 2270원 거스름돈
▪
1000원 2개
▪
100원 2개
▪
50원 1개
▪
10원 2개
◦
MSD( Most Significant Digit ) 사용
▪
가장 중요한 단위를 먼저 계산하는 것
▪
자신보다 더 큰 지폐 혹은 동전으로 거스름돈을 주면
더 적은 개수로 받는다 생각
•
하지만 이 경우는 언제나 적용이 가능하지 않음
◦
ex) 거스름돈 120원, 동전종류(50원, 40원, 10원)
▪
MSD → 50원 2개, 10원 2개
▪
실제정답 → 40원 3개