lsh424

동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작다. 여러 개의 소문제로 분할하여...??? 응?? DP를 처음 공부하신다면 이게 무슨 말이지? 이해가 잘 안 가실 수 있으실 텐데요. 그래서 하나의 좋은 예시가 있습니다 ㅎㅎ 바로 피보나치 수열인데요. 피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있습니다. 이제 이런 피보나치 수열을 다음과 같이 분해해서 트리 형태로 나타내 보면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 볼 수 있습니다. 이 말이 즉, 위에서 설명한..