코딩 테스트를 위한 그리디 알고리즘 정의

그리디(greedy) 알고리즘, 즉 말 그대로 탐욕법 혹은 욕심쟁이라는 알고리즘이다. 이 알고리즘을 사용하면 매 순간 가장 좋아보이는 결과물을 선택하고 이 선택이 나중에 미칠 요소는 고려하지 않는다. 매우 보편적인 알고리즘으로 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형이지만 특정 알고리즘 (예시: 정렬, 최단 경로 구하기 등)은 알고리즘의 사용방법을 정확히 알고 있어야 풀 가능성이 높다. 가장 좋은 결과물을 도출해내는 것을 기준으로 하는 알고리즘으로써 종류는 매우 다양하지만 기본적으로 '가장 큰 순서' 혹은 '가장 작은 순서'라는 의미를 가지고 있는 문제들이다. 1번 예시: 거스름돈 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하고 손님에게 거슬러 줄 동전의..