divide and conquer
-
알고리즘, 문제해결패턴, Divide and ConquerData Structure & Algorithm 2024. 6. 12. 22:02
Divide and ConquerDivide and Conquer의 기본 개념은 다음과 같습니다:분할(Divide): 해결해야 할 문제를 동일한 유형의 더 작은 부분 문제로 나눕니다.정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다. 부분 문제가 충분히 작으면 직접 해결합니다.결합(Combine): 부분 문제의 해를 합쳐서 원래 문제의 해를 얻습니다.예제예제 1: 병합 정렬 (Merge Sort)병합 정렬은 Divide and Conquer를 사용하는 대표적인 정렬 알고리즘입니다. 배열을 반으로 나눈 후 각각을 정렬하고, 정렬된 부분 배열을 합칩니다.function merge(arr1, arr2) { let idx1 = 0; let idx2 = 0; let result = []; whi..