오늘은 DP와 분할정복에 대해서 알아보겠습니다. 또한 DP와 분할정복이 언뜻 보면 비슷한 것으로 생각할 수도 있는데, 이의 차이점을 조금 명확하게 확인해봅시다. 분할정복 분할정복이란 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘입니다. 분할정복은 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하고 이들의 해를 취합하여 원래 문제의 해를 얻습니다. 즉, 하나의 문제를 더 이상 분할할 수 없는 부분 문제로 쪼개고, 해당 부분 문제에 대한 부분 해를 구하여 최종 문제에 대한 해를 구하는 방식이죠. 아래의 그림이 분할 정복을 잘 설명해주고 있습니다. DP(Dynamic Programming) 동적계획 알고리즘 즉, DP는 입력 크기가 작은 부분 문제들을 해결한 후에, 그 해들을 이용하여 보다..
