그리디 알고리즘 증명(작성 예정)

그리디 접근 방법은 매우 명쾌하다. 매 step마다, 매 스텝에서 최적인 해를 찾는 것이다. 그런데 알다시피 문제는 이것이 global optimization을 만족하냐는 것이다.

그렇다면 가장 중요한 부분은 그리디 알고리즘으로 구한 해가 global optimization이 될 것인지 증명하는 것이라 볼 수 있겠는데, 이를 다루는 강의는 찾아보기가 매우 힘들다. 

그나마 겨우겨우 찾은 곳이 아래 링크.

https://hyunw.kim/blog/2018/09/18/Algorithm_Analysis07_GreedyAlgorithm1.html

Algorithm Analysis - Greedy Algorithm 1

따라서 자료를 좀 더 찾아보고 정리를 해볼 예정이다.