[Algorithm] Greedy (탐욕법)

그리디(탐욕법)가 무엇인가?

• 어떤 문제가 있을 때, 단순 무식하게 문제를 푸는 알고리즘
  • 지금 당장 좋은 것만 고르는 방법이다.
  • 현재 선택이 나중에 미칠 영향은 고려하지 않는다.

---

언제 적용하면 되는가?

• 문제의 유형이 매우 다양해서 많이 풀어보며 감을 익히자.
• 우선 문제를 많이 풀어서 감을 익히자!
  • 사전 지식 없이도 풀 수 있는 경우가 존재하지만, 아이디어 떠올리려면 연습이 필요!
• 문제를 읽었는데 어떤 유형인지 감이 안 잡히면 Greedy -> DP / Graph 순서로 의심해보자
• Greedy로 풀기 위해서는 탐욕적인 방법을 떠올리고, 정당한지 검토할 수 있어야한다!

---

연습문제

1. 거스름 돈

2. 큰 수의 법칙 (해설 있음)

3. 숫자카드게임

4. 1이 될 때까지 (해설 있음)

---

이것이 코딩테스트다를 읽고 작성했습니다.

•