Divide-and-Conquer Algorithm 편집하기

'''Divide-and-Conquer Algorithm''' is a problem-solving approach that breaks a complex problem into smaller subproblems, solves them recursively, and then combines the results to obtain the final solution. It is widely used in computer science for designing efficient algorithms.
==Key Concepts==
*'''Divide:''' The original problem is split into smaller, independent or overlapping subproblems.
*'''Conquer:''' Each subproblem is solved recursively.
*'''Combine:''' The solutions of the subproblems are merged to obtain the final result.
==Steps in a Divide-and-Conquer Algorithm==
#Divide the problem into smaller subproblems of the same type.
#Recursively solve each subproblem.
#Combine the results of the subproblems to solve the original problem.
==Examples==
*'''Merge Sort'''
**Divides the array into two halves.
**Recursively sorts each half.
**Merges the two sorted halves into a single sorted array.
**Complexity: O(n log n).

*'''Quick Sort'''
**Selects a pivot element.
**Partitions the array such that elements smaller than the pivot are on the left and larger ones are on the right.
**Recursively applies quick sort to both partitions.
**Complexity: O(n log n) (average case).

*'''Binary Search'''
**Compares the target value with the middle element.
**If the target is smaller, searches in the left half; otherwise, searches in the right half.
**Repeats until the target is found or the search space is empty.
**Complexity: O(log n).
==Advantages==
*'''Efficiency:''' Many divide-and-conquer algorithms have better time complexity than iterative approaches.
*'''Parallelism:''' The independent subproblems can be solved concurrently.
*'''Simplification:''' Reduces complex problems into manageable subproblems.
==Limitations==
*'''Recursion Overhead:''' Excessive recursive calls can lead to high memory usage.
*'''Merge Overhead:''' Combining subproblem results may require extra computations.
*'''Not Always Optimal:''' Some problems do not naturally fit the divide-and-conquer paradigm.
==Applications==
Divide-and-conquer algorithms are used in:
*'''Sorting Algorithms:''' Merge Sort, Quick Sort.
*'''Searching Algorithms:''' Binary Search.
*'''Matrix Multiplication:''' Strassen’s algorithm.
*'''Computational Geometry:''' Closest pair of points problem.
*'''Graph Algorithms:''' Finding strongly connected components.
==Comparison with Other Approaches==
{| class="wikitable"
!Approach!!Description!!Example Algorithms
|-
|Divide and Conquer||Breaks the problem into smaller subproblems, solves recursively, then combines||Merge Sort, Quick Sort, Binary Search
|-
|Dynamic Programming||Breaks the problem into overlapping subproblems and stores results to avoid recomputation||Fibonacci Sequence, Matrix Chain Multiplication
|-
|Greedy Algorithms||Makes the best local choice at each step to find a global solution||Kruskal’s Algorithm, Dijkstra’s Algorithm
|}
==See Also==
*[[Merge Sort]]
*[[Quick Sort]]
*[[Binary Search]]
*[[Dynamic Programming]]
*[[Greedy Algorithm]]
*[[Recursion]]
[[분류:Algorithm]]