📑 동적계획법_2294_동전2
동적계획법 주어진 문제를 여러 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 알고리즘 어떤 문제를 풀기 위해 해결해야 하는 부분 문제의 개수가 k개라고 한다면, 전체적으로 풀어야하는 문제의 개수는 O(kN)개가 될 것이다. 이때 k가 충분히 무시할 수 있을 정도로 작은 수이고, 각가의 문제를 푸는데 걸리는 시간이 O(1)이라면, 문제의 결과를 저장할 O(N)의 메모리가 필요하며, O(N)만큼의 시간이 소요된다. 분할 정복 vs DP 분할하는 점은 동일하지만 전자는 겹치는 부분문제가 없지만, 후자는 있다는 것이다. 따라서 메모이제이션 기법으로 비효율적인 반복 연산을 줄인다. Greedy vs DP 모든 경우를 메모리까지 소비해가며 샅샅이 체크하는 점에서 전자보다 후자가 실행 시간은 길지만, ..
