[알고리즘] 분할정복, 동적 프로그래밍 조사

1. 분할정복 개념

분할정복은 문제를 해결하는 대표적인 알고리즘 기법 중 하나로, 복잡한 문제를 간단한 하위 문제로 나누어 각각 해결한 후, 그 해결책을 결합하여 전체 문제의 해를 찾는 방식을 의미한다. 이 방법은 문제를 작은 단위로 쪼개기 때문에 문제의 구조를 명확히 파악할 수 있으며, 재귀적인 호출을 통해 효율적으로 해결할 수 있다. 분할정복의 핵심 원리는 문제를 여러 개의 크기가 작은 하위 문제로 나누고, 각 하위 문제를 재귀적으로 해결한 뒤, 그 결과를 통합하여 최종 답을 도출하는 것이다. 예를 들어, 병합정렬(Merge Sort)은 분할정복 방법을 사용하며, 전체 배열을 반씩 나누어 각각 정렬한 후, 병합하는 과정을 반복한다. 이와 같은 방식은 평균 시간 복잡도를 O(n log n)으로 유지하며, 특히 대용량 데이터 정렬에 매우 효율적이어서 금융, 통계, 과학 분야에서 활발히 활용된다. 또 하나의 사례로, 이진 탐색(Binary Search)은 정렬된 배열 내에서 원하는 값을 찾기 위해 배열을 가운데 기준으로 계속 반으로 나누며 탐색하는데, 이 역시 분할정복 원리를 따른다. 이진 탐색은 검색 시간이 O(log n)으로 매우 빠르기 때문에 대규모 데이터 베…