그리디

패스트캠퍼스 챌린지 3일차

날짜 : 2021 년 11 월 3 일 시청 강의 : 탐욕 알고리즘의 이해 (1) , 탐욕 알고리즘의 이해 (2) Greedy Algorithms 탐욕 알고리즘은 쉬운 문제는 정렬을 이용, 보통 DP를 사용하여 문제를 푸는 것 같다. 본 강의에 나온 예제는 누가봐도 정렬로 푸는 문제였지만 보통 탐욕 알고리즘은 코테에서 만났을 때 탐욕 기법으로 풀 것이라 상상도 못하는 것들이 많다고 하니 전형적인 유형들만 몇개 공부하면 될 것 같다. 문제 유형 : 1. 거스름돈 줄이기 손님이 지불한 금액에서 물건값을 제한 차액을 지불하는 문재. 동전을 최소한으로 주고 싶을 때 -> 주로, 500원 1000원이 아니라 400원 300원 이런식으로 나오기 때문에 정렬로 풀 수 없고 DP를 이용하여 풀어야한다 2. 설탕배달 ht..