728x90 머지소트1 divide-and-conquer 분할 정복 (feat. merge sort) 분할정복의 3단계 Divide : 문제를 동일한 문제의 작은 인스턴스인 여러 하위 문제로 나눔. Conquer : 하위 문제들을 재귀적으로 풀어서 정복. (하위 문제의 크기가 충분히 작다면, 간단한 방법으로 하위 문제를 해결) Combine : 하위 문제에 대한 해결책을 원래 문제에 대한 해결책으로 결합. Merge Sort Merge Sort의 문제 해결법은 원본 배열(A)을 복사 한뒤 절반으로 나눈다 (L, R) 절반으로 나눈 두 배열(L,R)이 정렬이 되어있다는 가정하에 두 배열의 값을 비교하면서 A배열을 정렬한다. 이 정렬 매커니즘을 L,R에도 재귀로 적용 시킨다면 그것이 merge sort L,R 배열의 크기가 가장 작아질때까지 분할하기로 하고(Divide) 재귀를 이용하여 가장 하위노드 L,R.. 2022. 11. 10. 이전 1 다음 728x90
