코딩딩딩

1. 그리디 알고리즘 'greedy'란 한국어로 '탐욕스러운'으로 해석이 된다. 탐욕스러운 알고리즘? 어떻게 해야 탐욕적인 거지? 등 여러 의문이 생길 수 있다. 정리를 하자면 그리디 알고리즘이란 "선택의 순간에서 최적의 선택만을 하는 방법"을 의미한다. 단, 매 순간마다 최적의 선택을 하지만 남아 있는 선택들은 고려를 하지 않기 때문에결과가 항상 최적이라는 보장은 없다. 그러므로, 그리디 알고리즘을 사용하기 위해선 조건이 따라붙어야 한다. 2. 그리디 알고리즘의 최적해 도달 조건 1)  탐욕적 선택 속성(greedy choice property)탐욕적인 선택이 항상 최적의 해를 보장한다. 즉, 각각의 선택이 서로 영향을 주지 않는다. 2) 최적 부분 구조(optimal substructure)부분 문제..