코딩 테스트/코딩 테스트 알고리즘
-
그리디 알고리즘 (Greedy Algorithm)코딩 테스트/코딩 테스트 알고리즘 2022. 10. 26. 12:03
01. 그리디 알고리즘이란? 현재 상황에서 가장 좋은 것만 고르는 방식이다. 탐욕법이라고도 한다. 사전에 특정 알고리즘을 공부하지 않아도 풀이를 떠올릴 수 있는 경우가 많다. 02. 그리디 알고리즘의 예시 : 거스름돈 문제 내가 가게의 계산 직원이라고 생각했을 때, 거스름돈이 500원, 100원, 50원, 10원 단위로 있다고 생각하자. 손님에게 거슬러 줘야 할 돈이 N원일 때, 가장 적은 동전을 써서 거슬러줄 수 있는 경우는? 전형적인 그리디 알고리즘의 예시 "가장 큰 화폐 단위부터" 돈을 거슬러 주면 됨 1370원을 거슬러 줘야 한다고 가정할 때 가장 큰 단위인 500원을 2번 거슬러 준다. (남은 돈 370원) 두 번째 큰 단위인 100원을 3번 거슬러 준다 (남은 돈 70원) 세 번째 큰 단위인 ..