알고리즘

말 그대로 구간의 누적합을 구하는 문제입니다. 지정된 인덱스부터 하나하나 더하는 방식은 최악의 경우 O(n^2) 의 시간복잡도를 갖기 때문에 입력의 범위가 클 때 사용할 수 없지만 Prefix sum 방식을 사용하면 O(n) 으로 해결할 수 있습니다.

말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.최적해를 구하는 데에 사용되는 근사적인 방법이다.

입력으로 주어진 동전의 종류와 개수를 가지고 목표 금액을 만들 수 있는 조합의 개수를 구하는 문제!