분할 정복 알고리즘은 이름에서 부터 알 수 있듯, 그대로 해결할 수 없는 문제를 거의 같은 크기의 여러개의 작은 문제로 분할하여 해결하는 방법이다. 또한 분할 정복 알고리즘의 경우 보통 재귀함수를 통해서 구현되지만 거의 같은 크기의 문제로 나눠야 한다는 것에 차이가 있다. 분할 정복의 구성 1) 주어진 문제를 여러개의 부분 문제로 나눈다. (divide) 2) 재귀 함수를 통해서 각각의 부분 문제를 해결한다 (conquer) 3) 각 부분의 문제의 답으로 부터 전체 문제의 답을 계산한다. (merge) 문할 정복의 적용을 위해 요구되는 특성 1) 문제를 둘 이상으로 나누는 자연스러운 방법이 있어야한다. 2) 부분 문제의 답을 조합하여 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 문할 정복 문..