greedy 알고리즘이란?

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다.

문제해결단계

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

greedy 알고리즘의 특징

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.

주의점
선택한 상황이 그 순간 가장 최적의 상황이 되어야 하고 이 답이 최종적으로 해답이 되어야합니다.만약 그렇지않으면 그리디알고리즘을 쓸 수 없습니다

예시

• 동전 개수의 최솟값을 구하기

function partTimeJob(k) {
  // TODO: 여기에 코드를 작성하세요.
  // 입력값k 는 가격
  //출력값은 동전의 개수!
  //가장 큰 500원부터 가격을 빼준다
  //배열로?

  let arr =[500 , 100 ,50 ,10 , 5, 1]
  let count = 0
for(let i of arr){
  count = count + Math.floor(k / i)
  k = k - Math.floor(k / i) * i

}
return count
}

이 문제에서 그리디알고리즘을 사용할 수 있는 이유?
모든 동전들이 배수이기 때문 만약 배수가 아니였다면 현재상황에서 최선의 선택이 될진 몰라도 최종적인 답에서 오류가 나게된다