• 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘
• 잘따져보지 않으면 반례 발생 → 최적의 해를 보장하지 않음 → 그리디를 써도 되냐 안되냐 판단해야함

핵심 이론

그리디 알고리즘 수행 과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해 선택
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정 반복

[032] 동전 개수의 최솟값 구하기

• https://www.acmicpc.net/problem/11047
• 가장 큰 동전부터 차례대로 사용
• i ≥ 2인 경우에 Ai는 Ai-1의 배수 형태이기 때문에 반례가 없어 그리디 알고리즘 사용 가능

[033] 카드 정렬하기

• https://www.acmicpc.net/problem/1715
• 계산 할 때마다 정렬이 필요 → 우선순위 큐

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(1); // 삽입 성공 시 true 반환 / 실패 시 IllegalStateException발생
pq.offer(1); // 삽입 성공 시 true 반환 / 실패 시 false 반환

pq.remove(); // 첫번째 값 제거, 비어있다면 예외 발생
pq.poll(); // 첫번째 값 반환하고 제거, 비어있다면 null
pq.element(); // 첫번째 값 반환만함, 큐가 비어있으면 예외 발생
pq.peek(); // 첫번째 값 반환만함, 큐가 비어있으면 null 반환
pq.clear(); // 초기화

[034] 수를 묶어서 최댓값 만들기