Dynamic Programming

[알고리즘][백준][JAVA] 9095번 : 1,2,3 더하기 / Dynamic Programming, 다이나믹 프로그래밍

다이나믹 프로그래밍 (DP) 해당 문제의 알고리즘을 확인해보면 '다이나믹 프로그래밍' 이라고 되어 있다. 이는 동적 계획법이라고도 불리며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 이는 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용하는 방식으로 자주 쓰인다. (기억해가면서 풀기) DP를 쓰는 이유 일반적인 재귀 방식 또한 DP와 매우 유사하다. 하지만 둘의 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 다음과 같다. 1, 1, ..