BOJ 2293
-
[Algorithm] - DPAlgorithm/Algorithm 2022. 9. 1. 22:30
DP(Dynamic Programming) 동적 프로그래밍으로, 큰문제를 작은 문제로 나누어 푸는 문제이다. Devide & Conquer과 비슷하지만, DP는 작은 문제로 나누어 반복되는 것을 이용해가면서 푸는 것이다. 반복되는 작업을 푸는 것은 Recursion으로 풀이가 가능하지만, 반복되는 작업을 또 하기보다 값을 저장하여 두고 다시 재사용하는 방식으로 푸는 것이 특징. ( Memoization) 대표 문제 Fibonacci / Knapsack problem 아래 그림과 같은 형태로 재귀로 풀이가 가능하지만, 매번 재귀로 풀이시 동일한 값을 또 사용할 수 있다. BOJ 2293번 각 Data에서 단계를 나누어 가능한 경우의 수를 늘려준다. idx 0 1 2 3 4 5 6 7 8 9 10 (k) d..