책의 2부에서 처음으로 등장하는 그리디 알고리즘에 대해 공부하는 시간이다.
1. 그리디
- 그리디(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 특징
- 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
- 매우 다양 => 사전지식 없이도 풀 수 있지만 그만큼 다양한 문제들로 훈련해야함.
- 창의력과 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함.
- 정렬 알고리즘과 짝을 이뤄 출제가 됨.
- 문제 파악법
- 단순히 현재 상황에서 가장 좋아 보이는 것만 선택해도 문제를 풀 수 있는가?
- "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 알게 모르게 제시하는가?
- 대체로 위와 같은 기준은 정렬과 연관이 있어 정렬 알고리즘과 짝을 이뤄 출제가 됨.
- 그리디 문제의 해법을 찾을 때 그 해법이 정당한지 파악
- 만약 그리디 알고리즘으로 해결 방법을 찾을 수 없다면? 다이나믹 프로그래밍이나 그래프 알고리즘인지 확인할 것!
2. 그리디 유형의 알고리즘 문제
- 예제 3-1 거스름 돈
- 실전문제 큰 수의 법칙
- 실전문제 숫자 카드 게임
- 실전문제 1이 될 때까지
- Q 01 모험가 길드
- Q 02 곱하기 혹은 더하기
- Q 03 문자열 뒤집기
- Q 04 만들 수 없는 금액
- Q 05 볼링공 고르기
- Q 05 무지의 먹방 라이브
