Soongle's Morgorithm

DP(동적계획법)란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 두 가지 방법으로 문제를 해결할 수 있는데, Top-down은 가장 큰 문제를 나누어 작은 문제를 호출해 답을 찾는 방식이고 Bottom-up은 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식이다. Top-down 방식은 재귀함수를 이용해 구현한다. 예를 들어, 피보나치 함수를 f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1 위와 같은 점화식으로 세웠을 때 Top-down 방식으로 코드를 구현하면 다음과 같다. int f(int n) { if(n