■ Greedy는 한국말로 "탐욕스러운"이라는 뜻이다. 따라서 그리디 알고리즘은 말 그대로 눈앞의 이익만 쫓는 아주 탐욕스러운 알고리즘이라는 것이다. 그렇다면 Dynamic Programming(다이나믹 프로그래밍)과 Greedy(그리디)는 무엇이 다른 걸까?? 조금 딱딱하게 이론적으로 설명하자면 다이나믹 프로그래밍은 하위 문제에 대한 최적의 해결책을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션(global optimum solution)에 대한 선택을 하고 그리디는 각 단계마다 최적해를 찾는 문제로 접근해 문제를 작게 줄여나가는 형태이다. 이후 설명을 통해 좀 더 이해해보자. ■■ 대표적인 매우 유명한 문제인 배낭 문제를 예제로 그리디 알고리즘을 구현해보겠다. 위 그림과 같이 15k..
