gyeong3un2

'당장 좋은 것만을 선택'하는 그리디 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로'와 같은 기준을 제시한다면, 정렬 알고리즘을 사용한다. 이때, 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디의 대표적인 문제로는 '거스름돈 문제'이다. 거스름돈 예제에서의 시간 복잡도는 O(K)로 이때 K는 화폐의 종류이다. 즉, 이 알고리즘의 시간 복잡도는 화폐의 종류에 영향을 받는다. 실전 문제 1. 큰 수의 법칙 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없음 ex) 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고, K가 3이라고 가정하자..