큰돌님 참고

https://blog.naver.com/jhc9639/222319124359?trackingCode=blog_bloghome_searchlist

알고리즘 해결 전략

• 문제를 풀 때

1. 완탐?
2. dp ?
3. 이분 탐색?
4. 그리디???

• 그러면 가장 작은 범위를 통해서 답을 구할 수 있을까???
  를 생각해보자. 그게 가능하다면 ,
  작은 범위부터 진행해서 전체까지 진행한다.
  또는 작은 범위에서 최대 까지 진행하는 시퀀스를 작성하자.

그리디란?

: 전체 에서 일부분의 최적값을 구하면 그것이 각 단계를 거치면서
전체 최적해를 구하는 문제다.

• 동전 문제를 생각해보면
  : 12100 원 가지고 있는데 아래 4개의 화폐를 최소한으로 사용하는 방법은?

• 사용 가능 화폐가
  10000원, 5000원, 1000원, 100원이라고 하면

• 위의 4개 화폐를 각 단계라고 할 수 있다.
  경험적? 사고? 그게 아니라면 가장 작은 화폐수 나오게 하려면
  가장 큰 10000원을 가지고 한번 처리한 후,
  다음 단계인 5000원 처리
  다음 단계인 1000원 처리

이러한 순서로 하면 된다는 것이다.

그리디 2번

• 동전 문제는 각 단계가 명확하다.

• 가장 작은 단위를 통해서 뭔가 답을 얻어 낼수 있다면
  이러한 문제도 그리디 문제다.

• 예시 문제
  : 백준 1080 행렬 문제
  : 백준 2875 대회 인턴