오늘은 그리디 알고리즘에 대해 공부한 내용을 빠르게 정리하고 마무리. 앞에서 배웠던 재귀 관련 알고리즘으로는 크게 두 가지가 있었다. 분할 정복(Divide and Conquer)과 동적계획법(Dynamic Programming)이 그것이다. 1. 분할정복은 큰 문제를 중복 없는 작은 문제들로 분할하는 방법이다. 재귀적으로 작은 문제부터 해결한다. 2. 반면, 동적계획법은 작은 문제들로 쪼개되 이 작은 문제들 중 중복되는 애들을 DP 테이블에 저장해두고 같은 값이 나왔을 때 계산 없이 바로 테이블에서 꺼낸다. 그러면 오늘 다룰 그리디 알고리즘은 어떤 친구일까? 이름처럼 말 그대로 Greedy하게 선택하는 알고리즘을 뜻한다. 즉, 현재 상태에서 가장 좋은 선택을 반복해서 해를 구성한다. 예제로 동전 교환 ..