그리디 알고리즘(greedy algorithm)

그리디 알고리즘(greedy algorithm, 욕심쟁이 알고리즘) - 매 순간 최선의 선택, 지금 이 순간 당장 최적인 답을 선택

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다.

 

동전 교환 문제

 

배낭 문제

 

array[i][s]는 배낭 크기가 s 일때, i 개의 물건을 넣었을 때, 가능한 최대 가치를 의미