[알고리즘] Divide and Conquer(분할정복)이란? | Merge Sort(병합정렬)

정의 Divide and Conquer(분할정복)은 해결하기 힘든 큰 문제를 작은 문제로 분할하여 해결(정복)한 후 병합하는 알고리즘이다. 접근법 분할정복은 보통 다음과 같은 3단계의 과정을 거친다. 1. Divide(분할) : 문제를 더 작은 문제들로 분할 2. Conquer(정복) : 분할한 작은 문제들을 해결한다. 3. Combine(병합) : 작은 문제들의 해결법을 병합해 큰 문제의 해결법을 찾는다. 특징 1. 문제를 나눌 때 보통 재귀(recursion)를 많이 사용한다. 2. 재귀(recursion)를 이용할 때 오버헤드가 커 메모리를 많이 사용할 수 있다. 예시 Merge Sort(병합 정렬) 병합 정렬은 분할정복의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병..

원문링크 : [알고리즘] Divide and Conquer(분할정복)이란? | Merge Sort(병합정렬)