때로는 당장 눈앞의 최선이, 최고의 결과를 가져온다
현재 차례의 최고의 답을 찾는 문제
왜그런지 증명하기가 어렵다고함.
예시: 다른금액의 동전이 여러개 주어였을 때 M원을 만드는 최소의 개수
왜 동전문제가 그리디문제의 대표문제인 것인가?
내가 생각한 답은 동전문 무조건 큰돈이 작은돈의 배수이다. 그렇기 때문에 적은 개수를 주기 위해선 큰돈부터 주면 된다.
그리디 문제는 쉬운문제만 풀어봐서 다른 문제들을 모르겠다. 아마도 내가 이게 그리디인가 생각하지 않고 푼 문제 중에서도 그리디 문제가 있는거같다. 앞으로 문제풀땐 어떤 알고리즘을 사용해야하는지 생각부터해보기.
