분할 정복 알고리즘의 특징에 대해 정리하고 분할 정복의 적용이 부적절한 경우에는 어떤 것이 있는지 조사하고 분할정복을 적용하는데 있어서 주의할 점에 대해 분석하고 정리하시오

1. 분할정복알고리즘

분할 정복 알고리즘은 문제를 더 작은 하위 문제로 나누어 각각의 하위 문제를 해결한 후, 그 해답을 결합하여 원래 문제의 해답을 구하는 접근 방법이다. 이 알고리즘의 핵심 아이디어는 복잡한 문제를 단순한 문제로 분할하여 해결할 수 있도록 돕는 것이다. 분할 정복 알고리즘은 일반적으로 세 단계로 진행된다. 첫 번째 단계에서는 주어진 문제를 여러 개의 하위 문제로 나눈다. 이때 하위 문제들은 원래 문제의 특정 부분을 대표하거나 크기가 더 작은 형태로 존재한다. 두 번째 단계에서는 각각의 하위 문제를 재귀적으로 해결한다. 이 과정에서는 하위 문제들이 더 이상 분할할 수 없을 정도로 작아질 때까지 계속해서 분할이 진행된다. 마지막 단계에서는 하위 문제의 해답들을 적절히 결합하여 원래 문제의 해답을 도출한다. 분할 정복 알고리즘의 대표적인 예로는 병합 정렬, 퀵 정렬, 이진 탐색 등이 있다. 병합 정렬은 배열을 반으로 나눠서 각각 정렬한 후 두 개의 정렬된 배열을 병합함으로써 정렬된 배열을 얻는다. 퀵 정렬은 피벗을 설정하여 기준값을 기준으로 배열을 나누고, 각 파트를 재귀적으로 정렬함으로써 전체 배열을 정렬…