탐욕법 그리디

그리디 알고리즘을 요번 알고리즘 문제를 풀면서 처음으로 보았던 문제 인 것 같습니다.
그리디는 현 상황에서 가장 좋은것을 고르는 문제로 많이 나와서, 잘 생각해보고 문제를 접근하는 것이 좋을 것 같다고 생각합니다:)

그리디 알고리즘이란?

· 탐욕적으로 문제를 푸는 알고리즘
- 탐욕적이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미

· 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서 고려 x

· 코딩 테스트에서 만나게 될 그리디 알고리즘 문제 유형의 특징:
- 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
- 문제 유형이 매우 다양하여 암기한다고 항상 잘 풀 수 있는 알고리즘 유형이 아니다.
때문에 많은 유형을 접해보고 문제를 풀어보며 훈련 해야 한다.
- 일반적으로 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
즉, 특정 문제에서 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다.
- 다익스트라 알고리즘처럼 그리디 알고리즘이면서 암기가 필요한 알고리즘도 일부 존재
- 여러 개의 데이터를 빠르게 정렬해야 하는 문제를 위해 정렬 라이브러리의 사용 방법 숙지
- 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시한다.
대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로, 자주 정렬 알고리즘과 짝을 이뤄 출제한다.

[출처] https://scshim.tistory.com/224?category=956102